PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: notsoloud
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093
DIFFICULTY:
1335
PREREQUISITES:
None
PROBLEM:
Given a binary string S, in one move you can reverse any substring of length 3. What’s the minimum distance between some pair of ones that you can achieve?
EXPLANATION:
Suppose we reverse the substring consisting of indices [i, i+1, i+2]. Notice that this is essentially the same as swapping S_i and S_{i+2}.
In particular, if a 1
is on an even position, then after a move it will remain on an even position; and the same holds for odd positions.
However, among the even positions we can swap ‘adjacent’ elements, which means we can rearrange them as we like. This applies to the odd positions as well.
So,
- If there is a
1
on an even position and a1
on an odd position, we can rearrange the string to make them adjacent, giving us an answer of 1 (which is obviously the minimum possible). - If the above condition doesn’t hold, then all the ones are on positions of the same parity. In this case, we can make the distance between them 2.
So, all that needs to be done is to iterate across the string and check whether there are ones at both even and odd positions.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
odd, even = 0, 0
for i in range(n):
if s[i] == '1':
if i%2 == 0: even = 1
else: odd = 1
print(1 if odd > 0 and even > 0 else 2)