@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.
3 Likes
It’s nice to editorials too early.
2 Likes
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<pair<long,pair<long,long> > > 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: CodeChef: Practical coding for everyone
7 Likes
I am getting NZEC error in this code.
https://www.codechef.com/viewsolution/13067855
can anyone explain why i am getting this error?
My code is working in 3/9 case can someone help me with this .
code link-> https://code.hackerearth.com/ec26cap?key=8873a98d212090ee34b470913e133bfb
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)
2 Likes
nice editorial…
if k is greater than (n+1)/2 then will the answer be 1?
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.
I need the explaination for the editorialist’s solution’s [[Binary Search]] Logic. Thanks in Advance.
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
Can someone tell me the error in my solution ? I have tried a lot but could not find anything erroneous . Please help !!! CodeChef: Practical coding for everyone
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. CodeChef: Practical coding for everyone
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
@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.
CodeChef: Practical coding for everyone.
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.
CodeChef: Practical coding for everyone.