Canadian Computing Competition: 2020 Stage 1, Senior #4
There are people sitting at a circular table for a long session of negotiations. Each person belongs to one of the three groups:
C. A group is happy if all of its members are sitting contiguously in a block of consecutive seats. You would like to make all groups happy by some sequence of swap operations. In each swap operation, two people exchange seats with each other. What is the minimum number of swaps required to make all groups happy?
The input consists of a single line containing characters, where each character is
C. The -th character denotes the group of the person initially sitting at the -th seat at the table, where seats are numbered in clockwise order.
For of the available marks, the input has no characters and .
For an additional of the available marks, the input has no characters.
For an additional of the available marks, .
Output a single integer, the minimum possible number of swaps.
Output for Sample Input
Explanation of Output for Sample Input
In one possible sequence, the first swap results in the seating layout
AABCBCBCCA. After the second swap, the layout is
For the sample input, why is
AABBBCCCCAthe correct final sort? Why doesn't it need to be
AAABBBCCCCfor the A group to be happy?
They are arranged in a ring, not in a row.
The table is circular.
I don't understand how "AABCBCBCCA" can become "AABBBCCCCA" in just one swap. Can someone explain?
Swap these 2 characters.
Oh I see, thank you.
Can we assume there will always be >2 of each type? (in the case that one exists)
It's not in the statement, so probably not. I don't know why they would exclude cases like .