CCC '20 S4 - Swapping Seats - Olympiads Online Judge

CCC '20 S4 - Swapping Seats

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

Problem type

Canadian Computing Competition: 2020 Stage 1, Senior #4

There are $N$ ~N~ people sitting at a circular table for a long session of negotiations. Each person belongs to one of the three groups: A, B, or 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?

Input Specification

The input consists of a single line containing $N$ ~N~ $(1 \le N \le 1\,000\,000)$ ~(1 \le N \le 1\,000\,000)~ characters, where each character is A, B, or C. The $i$ ~i~-th character denotes the group of the person initially sitting at the $i$ ~i~-th seat at the table, where seats are numbered in clockwise order.

For $4$ ~4~ of the $15$ ~15~ available marks, the input has no $C$ ~C~ characters and $N \le 5\,000$ ~N \le 5\,000~.

For an additional $4$ ~4~ of the $15$ ~15~ available marks, the input has no $C$ ~C~ characters.

For an additional $4$ ~4~ of the $15$ ~15~ available marks, $N \le 5\,000$ ~N \le 5\,000~.

Output Specification

Output a single integer, the minimum possible number of swaps.

Sample Input

BABCBCACCA

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 AABBBCCCCA.

Comments

2

298567239 commented on Feb. 12, 2021, 8:04 a.m.

For the sample input, why is AABBBCCCCA the correct final sort? Why doesn't it need to be AAABBBCCCC for the A group to be happy?

2

ryanguorocket commented on Feb. 12, 2021, 7:20 p.m.

They are arranged in a ring, not in a row.

7

BalintR commented on Feb. 12, 2021, 3:19 p.m.

The table is circular.

4

huisfle commented on Jan. 23, 2021, 2:42 a.m.

I don't understand how "AABCBCBCCA" can become "AABBBCCCCA" in just one swap. Can someone explain?

15
d commented on Jan. 23, 2021, 2:48 a.m.
Swap these 2 characters.

AABCBCBCCA ^ ^

2

huisfle commented on Jan. 23, 2021, 5:25 a.m.

Oh I see, thank you.

-1

noYou commented on July 5, 2020, 8:56 p.m.

Can we assume there will always be >2 of each type? (in the case that one exists)

7

aaronhe07 commented on July 12, 2020, 12:23 a.m.

It's not in the statement, so probably not. I don't know why they would exclude cases like $ABC$ ~ABC~.