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
DEVSTR
It’s practically the same almost.
Really nice way to solve this. Thanks for sharing your method.
And using “trueval” and “id” is really good.
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.
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
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
no code there…
@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.
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
@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.
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.
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?
@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.
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
and how we will know about a ?
Why These Editorial are Written in Alien Language?
@orange19 , @daljit1
consider the following case
32 8
11110000000000000000000000001111
your code gives 4 ,but the answer should be 3
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.
In second tester’s solution while counting 0’s and 1’s why he is continuously swapping count of these.