Editorial for CCC '20 S4 - Swapping Seats - Olympiads Online Judge

Editorial for CCC '20 S4 - Swapping Seats

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

Subtask 1

Let us designate an arbitrary index $i$ $i$ as our 'split point'. Let $C_x$ $C_{x}$ be the number of characters of type "x" in the input string. Now let us say that in the final configuration, $i$ $i$ is the first position with As. Then the range $[i, i + C_A)$ $[i, i + C_{A})$ must all be As in the final configuration, and we call it the 'A section'.

This means that we need to do only as many moves as there are Bs in the A section. Since there are no Cs, we only need to swap any Bs in the A section with As in the B section, and since they correspond 1 to 1, that is our answer.

For the first subtask, we brute force all values of $i$ $i$ and count the number of Bs trivially, then take the lowest number of moves.

Time Complexity: $\mathcal O(N^2)$ $O (N^{2})$

Subtask 2

For the second subtask, we count the number of Bs using a Prefix Sum Array. Let $P_B \text{ at } j$ $P_{B} at j$ be the number of Bs in the prefix of length $j$ $j$ . Then we can use this to count the number of Bs in the A section in $\mathcal O(1)$ $O (1)$ time.

Time Complexity: $\mathcal O(N)$ $O (N)$

Subtask 3

For this subtask, we have to consider Cs. We take a different approach.

We go through all of the permutations of ABC. Without loss of generality, assume our permutation is ABC. The other 5 cases are analogous. Then we let the first $i$ $i$ characters of our final configuration be A. We can brute force through all possible values of $i$ $i$ from $0$ $0$ to $C_A$ $C_{A}$ . Then we know the exact state of our final configuration. The A section now forms both a suffix and a prefix of the string, but it is still the same section and we will process it that way.

We now simulate the swaps. For each element in the A section that is not an A, we swap it with an A in the corresponding section if we can. If we cannot, we can swap it with a random A from the other section. We do the same for the B section, and we have our answer.

For this solution, we have to keep track of the positions of each letter in each section. We can do this with 3 vectors for the B and C sections, for 6 vectors total.

Time Complexity: $\mathcal O(N^2)$ $O (N^{2})$

Full Solution

For full marks, we build on the solution from the second subtask.

Let $N_x$ $N_{x}$ be the number of non-x characters in the x section, and let $S_{x,y}$ $S_{x, y}$ be the number of type y characters in the x section.

Note that now for any index $i$ $i$ , we still have the A section from $[i, i + C_A)$ $[i, i + C_{A})$ . However, we need to consider that the next section can be either B or C. We can simply try both for all values of $i$ $i$ . Without loss of generality, assume the next section is B.

Then the B section is from $[i + C_A, i + C_A + C_B)$ $[i + C_{A}, i + C_{A} + C_{B})$ .

In this case, we must move all non-As from the A section and all non-Bs from the B section. However, note that we can save moves by swapping As in the B section with Bs from the A section. Thus, our answer for a given value of $i$ $i$ is:

$\displaystyle N_A + N_B - \min(S_{A,B}, S_{B,A})$ $N_{A} + N_{B} - min (S_{A, B}, S_{B, A})$

We can use a PSA to compute the $S$ $S$ and $N$ $N$ values in $\mathcal O(1)$ $O (1)$ time. We can then brute force all values of $i$ $i$ and consider both A section followed by B section or A followed by C.

Time Complexity: $\mathcal O(N)$ $O (N)$

Comments

15

lemondeath commented on Oct. 24, 2020, 11:42 p.m.

I've found an easier expression for the number of swaps required: $N_C + max(S_{A,B}, S_{B,A})$ $N_{C} + m a x (S_{A, B}, S_{B, A})$ . Here is the derivation.

$N_A + N_B - min(S_{A,B}, S_{B,A})$ $N_{A} + N_{B} - m i n (S_{A, B}, S_{B, A})$

$(S_{A,B} + S_{A,C}) + (S_{B,A} + S_{B,C}) - min(S_{A,B}, S_{B,A})$ $(S_{A, B} + S_{A, C}) + (S_{B, A} + S_{B, C}) - m i n (S_{A, B}, S_{B, A})$

Notice that $x + y - min(x, y) = max(x, y)$ $x + y - m i n (x, y) = m a x (x, y)$ . Therefore the expression can be further rewritten as:

$S_{A,C} + S_{B,C} + max(S_{A,B}, S_{B,A})$ $S_{A, C} + S_{B, C} + m a x (S_{A, B}, S_{B, A})$

$N_C + max(S_{A,B}, S_{B,A})$ $N_{C} + m a x (S_{A, B}, S_{B, A})$

I think that this expression lends itself to an easier (albeit less rigorous) intuition: first swap all of the Cs in the A and B sections back into the C section, then fix up the A and B sections by making swaps between them.