MINDIST1 - Editorial

editorial
,
1

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 a 1 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)
2

Like a fly on a window, I spent more than two hours on this problem.
Now I’ve read the two lines summary of the editorial, I’ve finally understood the question.
I’m not a native english speaker, but for me, “the minimum distance between ANY two 1s” didn’t mean “the minimum distance between some pair of ones”.
First I thought the answer was the minimum possible distance between the 1s in both extremities. This interpretation was in contradiction with the test cases.
Next, what I imagined is: for any 1, find the other 1 whose distance is minimum, and write down the maximum of those minimums. The test case 3 would have given 1 after another substring: S[4,6]. I didn’t understand the “5-4=1”, which was main error.
I have eventually spent much time thinking, which is what I like. The few points I’ve lost doesn’t matter.

2 Likes
3

For future reference, if you find something about a statement unclear, you can ask a clarification under the “comments” section; the setter or an admin will generally reply to valid questions within a few minutes :slight_smile:

1 Like
4

Thanks