I calculated all the continuous lengths(1,2,6,7…) , then I went on reducing k(k–) to convert all segments(l_seg) of a particular length (z) into three segments of lengths 1,(2 of l_seg/2)(odd), (l_seg/2,l_seg/2 -1)(even) and removed the original length and it’s count by these three lengths of samecount . When the highest length reached 2 I calculated the minimum no of flips required to make it 1 by adding the alternate distances between segments of length 2 and then taking the minimum of two len, if it was less than k , ans is 1 or its two . at any point if k becomes 0 ans is the length of next big segment , if k becomes less than 0 than ans is that particular segment.
Please tell me where is it wrong , I was getting 5 of 9 cases correct.
Also your logic fails at input string 111111111 and k=2, your code gives output as 4 because according to your logic when k becomes 0 your input string becomes 111101011 or 110101111 but actually after two operations string can be reduced to 110111011 and the answer here would be 3
PS: I also used the same logic as yours.
I think you should ask this question by yourself. Of course It’s your code so it’s sole responsibility of you to debug it and find where it is going to wrong. Just try to put print statement at every step to check whether your code is giving write answer as you are expecting or not
I too faced the exact same problem . I implemented this using heap and was replacing the max element by the ones you suggested.And was getting right answer for 5/9 parts. It was only after the contest I figured out that dividing from the middle isn’t the best strategy as in the example k=2 and number is say 0000000000.
