LMP7E - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: kingmessi
Tester: pols_agyi_pols
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

For binary strings P, Q, R, let f(P, Q, R) denote the minimum cost of making Q = R using the following operations:

  • First, you may flip any single character in either P or Q, with a cost of 1.
    This can be done as many times as you like, each with cost 1.
  • After all flips are completed, you may swap Q_i and Q_j, but only if P_i = P_j.
    Swaps cost nothing.

Given binary strings A, B, C, compute f(A, B, C).

EXPLANATION:

Suppose we’ve already made several flip operations to begin with. Let’s see when making B = C with only swaps is possible.

We’re only allowed to swap between indices where A_i = A_j.
So, we obtain a partition of the indices into two sets: those where A_i is 0 and those where it is 1.

Within each set of indices, we can freely rearrange the elements of B.
So, making B = C is possible only when the counts of 0 and 1 match in B and C for each index set.
That is,

  • Let the indices with A_i = 0 be i_1, i_2, \ldots, i_m
  • Among these indices, suppose there are b_0 zeros and b_1 ones in B, and c_0 zeros and c_1 ones in C.
  • Then, we need b_0 = c_0 and b_1 = c_1 to hold for rearrangement here to be possible.
  • The same condition must also hold when looking at all indices with A_i = 1 separately as well.

Our goal is thus to find the minimum possible cost of flips needed to attain such a state.

To do this, we first redefine what we’re looking for a bit.

Looking at only the indices where A_i = 0 (after flips), the condition that B and C have an equal number of zeros/ones at these indices is equivalent to:

  • The number of indices such that B_i = 0 and C_i = 1 is equal to the number of indices such that B_i = 1 and C_i = 0.
    (Here, we’re only considering those indices such that A_i = 0).

Of course, the same applies to those indices such that A_i = 1 as well.

Thus, we obtain 8 ‘types’ of indices, depending on which of A_i/B_i/C_i are 0 or 1.
Among these 8 types, we don’t really need to care about those indices for which B_i = C_i already - it’s never optimal to operate on either A_i or B_i for such indices.

So, we’re left with only four types of indices: 001, 010, 101, 110 (for the sequence A_iB_iC_i).
Let the initial counts of each of these four types be x_1, x_2, x_3, x_4 respectively.

Observe that our goal is to perform the minimum number of flip operations to reach a state where x_1 = x_2 and x_3 = x_4, after which swaps can finish the job.

Let’s analyze how the x_i values change after a flip.

Flipping A_i changes the type of the index between 001 \leftrightarrow 101 and 010\leftrightarrow 110.
This corresponds to adding 1 to x_1 and subtracting 1 from x_3 (or vice versa), or adding 1 to x_2 and subtracting 1 from x_4 (or vice versa).

Flipping B_i just corresponds to reducing one of the counts by 1.

So, we have (x_1, x_2, x_3, x_4), and each operation allows us to transfer 1 between values of the same parity (1 and 3 or 2 and 4), or reduce one value by 1.
Our goal is to make x_1 = x_2 and x_3 = x_4 with minimum cost, as stated above.

This can be solved mathematically.

Let s_o = x_1 + x_3 denote the sum of odd-index variables, and s_e = x_2 + x_4 denote the sum of even-index variables.

Note that the final state must have s_o = s_e.
So, we definitely need at least |s_o - s_e| operations, since the only way to change this difference is to subtract 1 from a value (the transfer operation doesn’t change either sum).

Once we attain s_o = s_e, note that the difference between x_1 and x_2 will equal the difference between x_3 and x_4 (just that one is non-negative and the other is non-positive).
So, a single transfer operation will move both differences closer to 0 which is what we want.
The number of transfer operations needed is hence just the difference between x_1 and x_2.

Thus, the solution is as follows:

  • Perform as many reductions as needed to make s_o = s_e.
    During this process, attempt to minimize |x_1 - x_2|
  • After all reductions, we need an additional |x_1 - x_2| transfer operations, so add this to the answer.

This can easily be implemented in \mathcal{O}(N) by just greedily choosing which elements to decrease, which solves the problem.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = input()
    b = input()
    c = input()
    
    ct = [0]*4
    for i in range(n):
        if b[i] == c[i]: continue
        if a[i] == '0':
            if b[i] == '0': ct[0] += 1
            else: ct[1] += 1
        else:
            if b[i] == '0': ct[2] += 1
            else: ct[3] += 1
    
    ans = 0
    while ct[0] + ct[2] < ct[1] + ct[3]:
        if ct[1] > ct[0]:
            ct[1] -= 1
        else:
            ct[3] -= 1
        ans += 1
    
    while ct[0] + ct[2] > ct[1] + ct[3]:
        if ct[1] < ct[0]:
            ct[0] -= 1
        else:
            ct[2] -= 1
        ans += 1
    
    print(ans + abs(ct[0] - ct[1]))
1 Like