STROPERS - Editorial

What will happen in case when we have 2 substrings- 1110 and 0111.
In this case number of 1s are equal length is also equal and number of odd 1s positions are also equal.
so how can we transform 1110 to 0111?
Btw Thank you for this amazing explanation :slight_smile:

A=“0111” B=“1111”
Are they equivalent? if yes then How?
Thanks.

No

brother thanks for the reply, but I am little confused here. The question says " choose a substring of A which contains ‘1’ an even number of times and reverse this substring."
So, can’t I choose substring “11” twice from string A and then reversed it and then append it to form B.
Thanks.

You don’t have to form a new string by the given operation. This operation needs to be performed on string A itself. For example in “0111”, you can choose a substring 011, the resulting string would be “1101” after operation.

1 Like

Great approach @resda @infinite_king @an2609 @ankan2526
Still, I have a doubt.
Do we need to transform all the substrings of the given string in
111… 000000…100000… form?

'Cause if we need to, time complexity would reach to n^4.

We don’t need to , let me explain how i calculated

  1. let’s call number of consecutive zeros in front of n’th 1 as Kn ( and similarly after n’th 1 as Kn+1 ).

For example take string 0010001010 , in this string we have 3 one’s , there is two zero’s in front of first 1 , three zero’s in front of second one , one zero in front of third one and finally one zero after third one. Therefore k1 = 2 , k2 = 3 , k3 = 1 and k4 = 1.

NOTE :- Kn can also be zero like in 1101 , K1 = 0 , K2=0 , K3 = 1 , K4 = 0

  1. Now let’s consider any generic string K1_1_K2_1_K3_1…

  2. We can do the following operation for any string with 2 or more one’s.

  • consider the substring K1_1_K2_1 , this substring has even number of one’s , so we can do the reversing operation , resulting in K1_1_K2_1_K3_1… -> 1_K2_1_K1_K3_1 .
  1. What we have done in the above operation is to send the 1 to the left , if the number of 1’s in the string is n , then we have n-1 1’s left in the string , we can perform the above operation repeatedly to send all n-1 1’s to left (or right also) [except one 1 , we can send all one’s to left] , but observe what happens to the number of zero’s in front and after the first selected 1
  • K1_1_K2_1_K3_1… -> 1_K2_1_K1_K3_1

  • 1_K2_1_K1_K3_1_K4 -> 11_K3_K1_1_K2_K4

  • 11 _K3_K1_1_K2_K4_1_ K5 -> 11 1_K2_K4_1_K1_K3_ K5 , and so on

  1. So basically , the number of zero’s in front and after is the sum of zero’s at odd and even positions in the orginal string.

  2. If we do the operation , odd number of times we get the even position sum and vice versa.

  3. All we have to do is to find whether n-1 is odd or even , and take the sum of number of zero’s in even or odd positions , which will be the number of zero’s in between last two 1’s.

some examples ,

00100010010 -> 10001000010 -> 11000010000
1110010 -> 1110010 -> 1110010 -> 1110010

For the large sub string’s rather than recalculating the odd and even sum again , we can use the old sums and update them by looking at the updated characters.

Hope this is helpful.

2 Likes

I also did it in a greedy way,in which I was playing with compressed form of string and tryting to convert the compressed form of each string in 1010 form by following constant operation.
Here is the link :smile:
codechef.com/viewsolution/40423822

Thank you for this wonderful in-depth explanation @infinite_king. It really helped a lot!
Finally got AC.
Here is my solution
https://www.codechef.com/viewsolution/40497981

1 Like

Could you please explain what you said at 12:48 again as to why some parameter assigned to some zero in a substring would have the same value in the reversed string…

:+1:

1 Like

My code’s time complexity is near to n^4, as I am storing the values in dictionary for reusing.

1 Like

Okay :+1: :+1:
Got it now @ankan2526
Thanks

Find my O(N^2) solution along with well explained editorial in the solution (code) itself.

https://www.codechef.com/viewsolution/40739001