CCC ’21 J4 – Solution

Arranging Books is a coding problem that can be viewed here. It isn’t easy, and is literally impossible to solve it correctly by actually swapping books. Here is the problem:

Canadian Computing Competition: 2021 Stage 1, Junior #4

Valentina wants books on a shelf to be arranged in a particular way. Every time she sees a shelf of books, she rearranges the books so that all the large books appear on the left, followed by all the medium-sized books, and then all the small books on the right. She does this by repeatedly choosing any two books and exchanging their locations. Exchanging the locations of two books is called a swap.

Help Valentina determine the fewest number of swaps needed to arrange a shelf of books as she wishes.

There needs to be a certain method to solve this problem. To solve this, you need to split the books into sections. For example, say that there is a group of books: MMSLSLLMS

Create three variables: L_total, M_total, and S_total, where L_total is the total number of Ls in the string, M_total is the total number of Ms in the string, and so on. It will be splitted like this:

MMS | LSL | LMS
 ^     ^      ^
large medium small

Split the string so that the first L_total variables are stored in another string, called large. Then, create 4 more variables: m_in_l, s_in_l, m_in_s, and l_in_m. l stands for large, m stands for medium, and s stands for small. You can calculate these by using the count function for large, medium and small. Using just these four numbers, you can solve this problem!

Create a simple if statement using this logic:

if (m_in_l > l_in_m)
    {
        total = m_in_l + s_in_l + m_in_s + m_in_l - l_in_m;
    }
else
    {
        total = m_in_l + s_in_l + m_in_s;
    }

In this type of method, this program first finds the minimum number of swaps needed to sort all the L’s into place. This is calculated by simply adding m_in_l and s_in_l. The L’s can be removed from the string, and then, adding the number of M’s in S, you could get the answer. However, there is a chance where there are more M’s than L’s. To solve this problem, using the if statement can help.

Psedocode:

get books
larget = books.count('L')
mt = books.count('L')
st = books.count('S')
get m_in_l by counting the number of M's in larget
get s_in_l by counting the number of S's in larget
get m_in_s by counting the number of S's in st
get l_in_m by counting the number of L's in mt
if m_in_l > l_in_m
    total = m_in_l + s_in_l + m_in_s + m_in_l - l_in_m
else
    total = m_in_l + s_in_l + m_in_s
print total

Example code (C++):

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    string books, large, medium, small;
    cin >> books;
    int m_in_l, s_in_l, l_in_m, m_in_s;
    int larget = 0, mt = 0, st = 0;
    larget = count(books.begin(), books.end(), 'L');
    mt = count(books.begin(), books.end(), 'M');
    st = count(books.begin(), books.end(), 'S');
    int total;
    large = books.substr(0, larget);
    medium = books.substr(larget, mt);
    small = books.substr(larget + mt, st);
    m_in_l = count(large.begin(), large.end(), 'M');
    s_in_l = count(large.begin(), large.end(), 'S');
    l_in_m = count(medium.begin(), medium.end(), 'L');
    m_in_s = count(small.begin(), small.end(), 'M');
    if (m_in_l > l_in_m)
    {   
        total = m_in_l + s_in_l + m_in_s + m_in_l - l_in_m;
    }
    else
    {
        total = m_in_l + s_in_l + m_in_s;
    }
    cout << total << endl;
    return 0;
}