PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: abhigyan1245
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
simple
PREREQUISITES:
None
PROBLEM:
You’re given three binary strings of the same length.
In one move, you can choose two of them and swap one character from each.
Find the minimum number of moves needed to make each binary string contain only a single type of character.
EXPLANATION:
We’re only allowed to swap characters around between strings, which means the overall count of zeros and ones cannot change.
Let c_0 denote the number of zeros and c_1 denote the number of ones, across all three strings. We’ll have c_0 + c_1 = 3N.
Observe that if c_0 is not a multiple of N, no solution can exist: this is because in the final state we want every string to contain either no zeros or N zeros; so c_0 will increase by either 0 or N.
This gives us only four possible options for what c_0 can possibly be: 0, N, 2N, 3N.
Note that 0 and 3N are trivial cases (corresponding to all characters being 1 and all characters being 0, respectively) - for both of them the answer is just 0 since all characters will be equal.
Now, let’s look at c_0 = N.
There are N zeros (and so 2N ones). That means, in the end, there must be exactly one string that’s filled with zeros, and the other two will be filled with ones.
Let’s fix S_i (1 \leq i \leq 3) to be the string that’s all zeros in the end.
Now, suppose S_i has k ones.
Each swap operation can remove only one of them from S_i, so we need at least k swap operations to remove them all from it.
It’s not hard to see that we can use exactly k operations to remove them all: in every swap, choose a 1 remaining in S_i and a 0 that’s outside S_i (which will always exist, since there are N zeros and not all of them are in S_i), and swap them.
So, after k swaps, S_i will be all zeros - which in turn means the other two strings will be all ones, and we’re done!
So, if c_0 = N, the answer is just the minimum number of ones in any of the strings.
If c_0 = 2N the situation is similar, just that the answer is the minimum number of zeros in any of the strings (apply the same logic, but noting that this time there will be exactly one string that’s all ones and the other two will be all zeros).
In summary:
- Let c_0 be the number of zeros across all three strings.
- If c_0 is not a multiple of N, the answer is -1.
- If c_0 = 0 or c_0 = 3N, the answer is 0.
- If c_0 = N, the answer is the minimum number of ones in any of the strings.
- If c_0 = 2N, the answer is the minimum number of zeros in any of the strings.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = [input(), input(), input()]
z = sum(st.count('0') for st in s)
if z%n != 0:
print(-1)
continue
if z == 0 or z == 3*n:
print(0)
continue
if z == n:
ans = min(st.count('1') for st in s)
else:
ans = min(st.count('0') for st in s)
print(ans)