×

# SCHEDULE - Editorial

Testers: Sergey Kulik, Kamil Dębowski
Editorialist: Pawel Kacprzak

EASY

Binary search

# PROBLEM:

For a binary string $A$, let's define a block as a substring of $A$ containing either only $1$'s or only $0$'s, so $111$ and $0$ are blocks, while $10$ and $0010$ are not. Moreover, let a major block be a block of $A$, such that no block in $A$ is longer that it and $L$ be the length of a major block of $A$. Notice that there can be many major blocks, but all of them have the same length.

Then the problem can be reformulated as follow: for a given binary string $A$ of length $N$ and integer $K$, we have to return the minimum $L$ (the length of a major block) that we can get by performing at most $K$ bit flips on $A$.

For example, if $A = 11100$ and $K=1$, the best we can do is to either flip the first or the second bit to get for respectively $01100$ and $10100$. In both these strings, $L$ is $2$, which is the best we can get in this case.

# QUICK EXPLANATION:

First, check if getting $L=1$ is possible. If yes the problem is solved, otherwise, perform a binary search on the result checking if getting $L=M$ is possible in linear time.

# EXPLANATION:

First of all, let's take a closer look at the constraints. It is said that $K \leq 10^6$, but since also $N \leq 10^6$ and there is no point of flipping a single bit more than once, we can rewrite the constraint as $K \leq N$.

In the first subtask $N \leq 10$, so one can generate all possible strings we can get by performing at most $K$ flips on $A$, and compute the smallest $L$ among them. This is possible because there are at most $2^N$ such strings and computing $L$ for a single string takes $O(N)$ time. Thus the overall time complexity of solving all test cases will be $O(T \cdot 2^N \cdot N)$, which is completely fine for these constraints and $T \leq 11000$.

In the second subtask we have $N \le 10^6$, so the problem has to be solved in a clever way. The crucial observation is that for any $L$ and any block of $A$ with length $M$, $\lceil M / (L+1) \rceil$ flips are necessary to convert that block into a substring without blocks of length greater than $L$, and we can perform exactly that many flips to do that.

For example, if we have a block of length $5$, $00000$, and $L=2$, we flip its bits with indices $L+1, 2 \cdot (L+1), 3 \cdot (L+1) \ldots$, so in this particular case, we flip only its third bit to get $00100$. Similarly, if we have a block of length $6$, $000000$, and $L=2$, we flip its third and sixth bits to get $001001$.

Thus it looks like we can perform a binary search for the answer and for a fixed $M$, check if we can transform all the blocks in $A$ into block of length at most $X$ using at most $K$ flips by just iterating over all blocks in $A$ and computing the sum of needed swaps for all of these blocks. Notice that binary search is correct here, because if it is not possible to use at most $K$ swaps to get $A$ with $L=X$, then it is also not possible to use at most $K$ swaps to get $A$ with $L \lt X$. This will result in $O(N \cdot \log N)$ time complexity for a single test case, but since the sum of $N$ across all test cases is at most $10^6$, this will run fast enough. However, we are not finished yet, because there is a tricky case to handle.

Notice that when we divide $A$ into blocks, the blocks alternate in such a way that after a block consisting of $0$'s there is a block consisting of $1$'s, then one consisting of $0$'s again and so on. The observation we made says that for a block of length $M$, $\lceil M / (L+1) \rceil$ flips are necessary and sufficient to convert this block into blocks of sizes at most $L$. It is true for an isolated block, however, since in some cases we are forced to flip the first or the last bit of such block, that may ruin our solution because that bit can create another block with adjacent blocks.

Let's take a closer look where this situation can happen, so in what cases we are really forced to flip either the first of the last bit of a block? As mentioned above, for a block of length $M$ and a fixed $L$, we can flip bits with indices $L+1, 2 \cdot (L+1), 3 \cdot (L+1) \ldots$. It follows that we are flipping its last bit if $M \mod (L+1) = 0$. However, if this happens and $L \gt 1$, we can always flip bits with indices $L, 2 \cdot L, 3 \cdot L, \ldots$ and we avoid flipping the first and the last bits, which caused the problem. But what happens when $L = 1$? Well, then we cannot use that trick, however, this case is easy to handle: at the beginning, we can just check if $A$ can be transformed using at most $K$ flips to get $L=1$. Notice that there are just $2$ possible strings of given length with $L=1$, either a sequence of alternating $0$'s and $1$'s starting with $0$ or the same but starting with $1$. If this is the case we are done. Otherwise, we use binary search described above searching for the answer in a range $[2, N]$. For implementation details, please refer to multiple solutions linked below.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Setter's solution can be found here.
First tester's solution can be found here.
Second tester's solution can be found here.
Editorialist's solution can be found here.

This question is marked "community wiki".

72483990
accept rate: 12%

2

It's practically the same almost.

(14 Mar '17, 03:58) 4★
1

Thanks, @saikat77. The editorial of DEVSTR is quite easy to understand.

(18 Mar '17, 23:39)

 6 This question can also be solved very easily by priority queue. First lets calculate all the lengths of consecutive 1s and 0s.Lets now make a priority queue of pair of pairs. priority_queue > > pqueue; Now we need to insert the (value of length,(some big number, initial value)); some big number can be 100000 for instance. Now we just need to pop from the priority queue and decrement the big number and divide the initial value by the (big number- new big number+1) and insert in the priority queue (new value,(new big number,initial value)). when pqueue.top().first==1 break the loop. Solve for the answer 1 separately. Here is the code snap: while(k--) {  long currtop= pq.top().first; if(currtop<=2){ break; } long ix=pq.top().second.second; long trueval= val[ix]; long id= pq.top().second.first; id--; long im=100000-id; currtop= trueval/(im+1); pq.pop(); pq.push(make_pair(currtop,make_pair(id,ix))); }  And here is the AC code: https://www.codechef.com/viewsolution/13057467 answered 13 Mar '17, 16:38 5★abx_2109 275●1●11 accept rate: 0% can you explain how and why it works?What is the use of big number (13 Mar '17, 18:37) nil962★ it is simple greedy technique.The longest segment stays on the top of the priority queue, we pop it and divide it by the required factor.Now purpose of a big number is when the top and the second element of the queue are the same i.e suppose we have 4,4.Now we wish to pop that element first which has been divided by a lesser factor.Hence initially we select a big number in the priority queue. (13 Mar '17, 22:16) abx_21095★ Really nice way to solve this. Thanks for sharing your method. And using "trueval" and "id" is really good. :D (14 Mar '17, 06:45)
 2 @saurabh9456 .. that won't work.. consider the string "111111111" and K=2 .. the optimal answer is 3 and with ur algorithm the answer would be 4. answered 13 Mar '17, 16:14 81●2 accept rate: 0%
 2 It's nice to editorials too early. answered 13 Mar '17, 16:32 258●9 accept rate: 17%
 1 Alternative Solution: Maintain a set of all original segments.Think of 'k' as total resources you have to allot to these segments to minimise the maximum contigous same bits.One can calculate the closed form for maximum subsegment size of the original segment when 'x' resources are alloted to the segment.The first element always corresponds to the original segment having maximum sub-segment size.At each iteration we allot one more resources to the first segment and calculate its new position in the set.The procedure terminates when k=0 . Complexity : O(n*logn) answered 13 Mar '17, 18:05 4★ps_1234 49●3 accept rate: 0%
 1 @shibli786 Binary search is used to reduce the computation effort.If we know that a may be the possible answer then there is no use in checking for the numbers > a else check for the numbers < a . If a doesn't satisfy then check for the numbers>a till u find a minimum value that satisfy it. answered 14 Mar '17, 13:09 2★daljit1 43●5 accept rate: 0% and how we will know about a ? (14 Mar '17, 15:38) one can start with a equal to the size of the maximum consecutive block in the initial given string since our answer has to be less than or equal to it . (14 Mar '17, 18:13) daljit12★
 1 best editorial answered 03 Apr '17, 23:29 21●4 accept rate: 0%
 0 I had an algorithm to solve it by storing segments in heap, and dividing longest segment by two and storing both parts again in heap. Will it work? Is there a easy way to check if it is possible to make answer 1. If it does suggest. answered 13 Mar '17, 16:09 71●2 accept rate: 0% Make two strings str0 and str1 that are alternating 0's and 1's, str0 starts with 0 and str1 starts with 1. Now let cnt0 and cnt1. start comparing your input string str with str0. if str[i] != str0[1] cnt0++; similarly compare str and str1 and get cnt1; Now in variables cnt0 and cnt1 you actually have number of flips required to make string str alternating 0's and 1's starting with 0 or 1 respectively. Now if(k >= min(cnt0, cnt1)) then for sure you can make alternating string. thus in this case answer is 1. (14 Mar '17, 06:55)
 0 I am getting NZEC error in this code. https://www.codechef.com/viewsolution/13067855 can anyone explain why i am getting this error? answered 13 Mar '17, 16:54 1 accept rate: 0%
 0 My code is working in 3/9 case can someone help me with this . code link-> https://code.hackerearth.com/ec26cap?key=8873a98d212090ee34b470913e133bfb answered 13 Mar '17, 17:03 4★ajaman13 1 accept rate: 0% no code there... (14 Mar '17, 09:57)
 0 @ajaman13 ... There seems to be no code out there. answered 13 Mar '17, 19:58 2★chari407 437●2●6 accept rate: 0%
 0 nice editorial... answered 13 Mar '17, 20:12 31●2 accept rate: 0%
 0 if k is greater than (n+1)/2 then will the answer be 1? answered 13 Mar '17, 20:25 174●5 accept rate: 13%
 0 Yes @aminuteman . For any given sequence, for the answer to be 1, the minimum number of moves required will always be less than or equal to half the length of the sequence. So, if k is >(n+1)/2 , we will surely be left with one or two excess moves even in the worst case. It can also be put this way - For the answer to be 1, there must be n/2 ones and n/2 zeroes (considering n is even, when n is odd, there will be an extra 1 or 0). So, to change the sequence so that answer becomes 1, at max we require n/2 moves or (n+1)/2 moves. Hope you got it. answered 13 Mar '17, 20:43 2★chari407 437●2●6 accept rate: 0%
 0 I need the explaination for the editorialist's solution's [[Binary Search]] Logic. Thanks in Advance. answered 13 Mar '17, 21:22 41●2 accept rate: 0% my solution : https://www.codechef.com/viewsolution/13088704 (13 Mar '17, 21:48) the binary search logic: maxL = 1e6 minL = 1 m = (maxL + minL)/2 now calculate the number of bits need to change/flip to have m as the answer. if the count is less than k less then the answer can be less than m(even lower than m, so maxl =m ) else m cannot be the answer so answer lies in between m and maxL(minl=m). in the end minl is the answer (13 Mar '17, 21:51)
 0 it can also be solved by checking for each answer ( not more than the length of longest segment ) ... if we are checking for an answer (say target) ,we try to reduce all the lengths of segments greater than our target by dividing it into n parts which will require n-1 values of given 'k'(allowed flips). n = length of segment / (target + 1) if all the segments can be divided requiring not more than remaining k flips..then our target is achieved and we have the answer, otherwise we will check for the next target(i.e target + 1). here is the link to my code https://www.codechef.com/viewsolution/13072300 answered 13 Mar '17, 21:44 1 accept rate: 0%
 0 Wouldn't an approach like the following work? https://www.codechef.com/viewsolution/13050938 answered 13 Mar '17, 21:48 1 accept rate: 0%
 0 @padamchopra Can you explain your approach in words ? answered 13 Mar '17, 22:03 2★chari407 437●2●6 accept rate: 0%
 0 Can someone tell me the error in my solution ? I have tried a lot but could not find anything erroneous . Please help !!! https://www.codechef.com/viewsolution/13072800 answered 13 Mar '17, 23:37 1★orange19 1 accept rate: 0%
 0 Please tell me error in my code. I tried a lot but there are always few test cases giving me WA. https://www.codechef.com/viewsolution/13090588 answered 14 Mar '17, 07:36 2★d_vishal 1 accept rate: 0%
 0 Don't Know which test cases did i miss help me with my code. https://www.codechef.com/viewsolution/13074004 for k>1 and less than n find the consecutive block length in the initial string put them in a container and keep them sorted. max value of the container split from mid like for 9 --> 4,4 (111111111)-->(111101111) //pop 9 and push 4,4 into the container and for even in this way 8 ----> 3,4(11111111)--->(11101111) //pop 8 and push 3,4 keep it doing till you get the top value of your sorted container==l and keep the count of flips if flips exceed return false for the query of l else return true that we will be doing a binary search for l>1 . for l==1 do the same way as in the editorial compare with 2 possible solutions.when it ends you get the minimum value of l(maximum consecutive same bits) possible answered 14 Mar '17, 09:16 2★daljit1 43●5 accept rate: 0%
 0 @abx_2109 I have used almost same approach as yours still I'm getting 5/9 cases. can you tell me what is the problem with my code. https://www.codechef.com/viewsolution/13060282. answered 14 Mar '17, 10:22 1 accept rate: 0%
 0 Can Anyone please tell me whats wrong in my code and how to correct it? here is my link - https://www.codechef.com/viewsolution/13074954 answered 14 Mar '17, 10:22 2★ankush23 31●3 accept rate: 0% You have split the numbers in 2 halves from middle every-time but that's not correct.Consider this case 11111 and k=2 then your answer comes out to be 2.But actually answer will be 1 by rearranging the string as 10101.Hope you got this point now :) Your approach is partially correct but not fully correct. (14 Mar '17, 10:46) thanks @naksh9619 (14 Mar '17, 13:08) ankush232★
 0 @abx_2109 I have used almost same approach as yours still I'm getting 5/9 cases. can you tell me what is the problem with my code. https://www.codechef.com/viewsolution/13060282. answered 14 Mar '17, 10:28 1 accept rate: 0%
 0 I am still not getting why binary search is used here. As far as i know Binary Search is sued for searching element in an array. Can any one explain it more clearly? answered 14 Mar '17, 12:15 72●3 accept rate: 7%
 0 This problem can also be solved without binary search. What you have to do is simply start from i = 1 where i is no of the continuous element appearing in the string. Then apply the concept of dividing partition by k+1 and check for all possible values of i and print the answer when count <= k. Submission link: https://www.codechef.com/viewsolution/13015971 answered 14 Mar '17, 14:02 1●1 accept rate: 0%
 0 @orange19 , @daljit1 consider the following case 32 8 11110000000000000000000000001111 your code gives 4 ,but the answer should be 3 answered 14 Mar '17, 16:18 1 accept rate: 0%
 0 Yup , thanks @abhishek_8 , @daljit1 ...our approach does not consider the situations like 0001111111111111 (n=13 and k=5), I get an output 3 for this (0001101101110111) but it should be 2 (0011011011011011) .My approach is always flipping the elements that lie in the middle of a block but in cases like these optimal answer is obtained by flipping the start or end of a block. answered 14 Mar '17, 16:26 1★orange19 1 accept rate: 0%
 0 In second tester's solution while counting 0's and 1's why he is continuously swapping count of these. answered 14 Mar '17, 17:50 4★nuclode 76●3 accept rate: 16%
 0 Can someone please explain what binary search is doing and how ? answered 14 Mar '17, 18:05 3★dhunni 1 accept rate: 0%
 0 @abx_2109 you said tha-- Now purpose of a big number is when the top and the second element of the queue are the same i.e suppose we have 4,4.Now we wish to pop that element first which has been divided by a lesser factor. but why to pop only that element which have a lesser factor. suppose we have 4,4 then why we cant choose anyone. answered 14 Mar '17, 18:10 2★kr6244 1 accept rate: 0%
 0 @abhishek_8 and @orange19 thanks for finding the pitfall in that approach:) answered 14 Mar '17, 18:21 2★daljit1 43●5 accept rate: 0%
 0 I a trying to solve this question from a long time and still cant get right answer. I have coded according to this editorial only. Please have a look at my code and help me get the bugs. This is my code: https://www.codechef.com/viewsolution/13123856 answered 19 Mar '17, 16:06 1 accept rate: 0%
 0 can anybody explain why we are taking lo = 2 and not 1; answered 20 Mar '17, 09:40 4★akki28 78●3 accept rate: 10%
 0 I tried to solve it with priority queues.But it didn't workout. I checked the two cases for the answer 1 and then execute this peice of code if answer is not 1.Everytime i take the largest block and divide it into 3 blocks of size i,j and 1 .Of course i used c++ but i wrote printf here because when i wrote cout the preview is not as i expected.What is going wrong with this code??  while(1) { if(k==0 || queue.top()<3) { break; } i=queue.top(); j=i-(i/2)-1; i/=2; queue.pop(); queue.push(i); queue.push(j); queue.push(1); k--; } printf("%d\n",queue.top());  answered 22 Mar '17, 16:23 1 accept rate: 0%
 0 Since L is the length of major block .So M would always be smaller than L?@Pawel Kacprzak link This answer is marked "community wiki". answered 27 Mar '17, 14:18 1 accept rate: 0%
 0 In the above editorial it is mentioned that for any block of A with length M, ceil(M/L+1) bits are necessary and sufficient to convert that block into the block such that no block is of size > L and we flip the indices (L+1),2(L+1), 3(L+1)... in this case we have to consider one based or zero based indexing?. When M mod(L+1)=0 then we flip the bits at indices L,2l,3l..., in this case we have to consider one based or zero based indexing?. answered 03 Apr '17, 12:31 2★arpit728 671●10●41 accept rate: 12% For a block like 0000000 and flips = 3, 0101010. I think its 0 based, provided u store it similarly. (03 Apr '17, 12:35) @vijju123 if block like 000000000 and l=2, we consider zero based indexing the reduced block sould be 001010100 but as M mod (l+1)=0 if we consider the approach proposed at starting without consider the critical case then using that approach we will flip (l+1),2*(l+1)... bits so the answer should be 000100100 but as stated in the editorial in this case boundary value should have got changed. But the second case works when we consider one based indexing, and reduced block be 001001001. I think there is something missing out in the editorial. Could you figure this out. (03 Apr '17, 12:50) arpit7282★ Here, the length is 9, which is divisible by l+1. For this case, the pattern is like 001001010, meaning the second last index is changed instead of last one. Read editorial of devstring, given in comment of the editorial's post. Its explanation was beautiful. (03 Apr '17, 13:01) @vijju123 look at the first three lines of last paragraph and then read my previous comment once again. (03 Apr '17, 13:17) arpit7282★ I read it. Okay, I see your doubt. I would say go through editorial of DEVSTR as they are literally the same Q, and that editorial explains it in a better way. The correct approach was shown in DEVSTR which was flipping bits as usual, except that if we are flipping last bit, we flip second-last instead. (03 Apr '17, 13:53) @vijju123 Okay, I will check that out. (03 Apr '17, 13:54) arpit7282★ showing 5 of 6 show all
 -2 Why These Editorial are Written in Alien Language? answered 14 Mar '17, 15:42 72●3 accept rate: 7%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,419
×2,897
×696
×124
×30

question asked: 10 Mar '17, 06:51

question was seen: 5,747 times

last updated: 03 Apr '17, 23:29