CCC '21 J4 - Arranging Books

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 3.0s
Memory limit: 1G

Problem type
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.

Input Specification

The input will consist of exactly one line containing at least one character. The following table shows how the available 15 marks are distributed.

Subtask Number of books Book types
7 marks at most 1\,000 characters each character will be L or S
2 marks at most 500\,000 characters each character will be L or S
4 marks at most 1\,000 characters each character will be L, M or S
2 marks at most 500\,000 characters each character will be L, M or S

Output Specification

Output a single integer which is equal to the minimum possible number of swaps needed to arrange the books so that all occurrences of L come first, followed by all occurrences of M, and then all occurrences of S.

Sample Input 1

LMMMS

Output for Sample Input 1

0

Explanation of Output for Sample Input 1

The books are already arranged according to Valentina's wishes.

Sample Input 2

LLSLM

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

By swapping the S and M, we end up with LLMLS. Then the M can be swapped with the L to its right. This is one way to use two swaps to arrange the books as Valentina wants them to be. It is not possible to use fewer swaps because both S and M need to be moved but using one swap to exchange them does not leave the books arranged as Valentina wants them to be.


Comments


  • 4
    Genius3435  commented on June 12, 2021, 9:55 p.m.

    This is the same as this one from usaco 2007 except with higher constraints. A very interesting problem, I have to say!


  • 4
    Marshmellon  commented on May 30, 2021, 8:26 p.m.

    I have a question. It says that subtask 1 and 2 only have L and S in them, but Sample input 2 (which is tested first) has M in it. So if I have a solution that only works for L and S, sample input 2 WAs and stops it from going any further. I had to add a if books == "LLSLM": print(2) raise SystemExit for it to work, is that intended?


  • 3
    planT_444  commented on March 14, 2021, 11:30 a.m.

    This is my favourite question of this year's CCC. It's the most fun one. J5 is ok but kind of tedious. This one is challenging and interesting


  • 0
    HOPE  commented on March 10, 2021, 11:15 p.m.

    I don't understand what is wrong with my algorithm

    I start by finding the highest index L and the lowest index S and swapping them if the index of S is less. Then If there is a M, then I swap the highest index M with the lowest index S if the index of S is once again less. If all those have passed false then I swap the highest index L with the lowest index M is the index of M is less. I don't understand what is wrong with this and for all the quick tests I have done for myself, it seemed to word so I am really confused on what is the problem.

    I got 7/15 points with this algorithm, getting the perfect marks on the first 3 batches.


    • 6
      Badmode  commented on March 10, 2021, 11:59 p.m. edited

      You're getting TLE (Time Limit Exceeded), try optimizing your algorithm and then check if you're getting WA or AC. How your algorithm works looks correct though.

      EDIT: You may find this helpful, if you hadn't already read it - https://dmoj.ca/tips