PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Jeevan Jyot Singh
Tester: Tejas Pandey
Editorialist: Nishank Suresh
DIFFICULTY:
1173
PREREQUISITES:
None
PROBLEM:
Given a binary string S, in one move you can pick two indices and flip their values. Is it possible to make the final string a palindrome?
EXPLANATION:
You might notice that performing an operation on two indices with two different values essentially swaps the values at these indices. This is already enough to make S into a palindrome whenever:
- N is odd; or
- N is even and contains both an even number of 0's and 1's
Proof
When N is even, for S to be a palindrome both the 0's and the 1's must occur an even number of times, since each 0/1 is paired with another 0/1.
It’s fairly easy to see that if this condition holds, then just swapping 0's with 1's can make S into a palindrome. For example, if there are x occurrences of 0 and y of 1, then make the first x/2 and last x/2 characters of S 0 using swaps. This is a palindrome.
Further, any odd-length string can always be made a palindrome.
Either the 0's or the 1's must occur an odd number of times in an odd-length string; suppose it’s the 0's.
Use one swap to make a 0 the middle character. Now, the remaining part of the string needs to be an even palindrome, and we satisfy the condition above so we’re done.
As it turns out, these conditions are both necessary and sufficient.
Proof
Note that the given operation doesn’t actually change the parities of the 0's and 1's.
Let c_0 and c_1 be the respective counts. Then, one operation can change them as follows:
- c_0 \to c_0 + 2 and c_1 \to c_1 - 2 (flipping two 1's to 0)
- c_0 \to c_0 - 2 and c_1 \to c_1 + 2 (flipping two 0's to 1)
- Leave c_0 and c_1 unchanged (swapping a 0 and a 1)
All three cases don’t change the parities. However, our earlier conditions only depended on the parities of c_0 and c_1. So, those cases are both necessary and sufficient.
Thus, the final solution is as follows: compute c_0 and c_1, the counts of 0 and 1 in the string. Then,
- If both c_0 and c_1 are odd, the answer is “No”.
- Otherwise, the answer is “Yes”.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
z, o = s.count('0'), s.count('1')
if z%2 == 1 and o%2 == 1:
print('NO')
else:
print('YES')