SCHEDULE - Editorial

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.

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.

1 Like

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: CodeChef: Practical coding for everyone

Why These Editorial are Written in Alien Language?

1 Like

@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.

Can someone please explain what binary search is doing and how ?

@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.

@abhishek_8 and @orange19 thanks for finding the pitfall in that approach:)

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: CodeChef: Practical coding for everyone

can anybody explain why we are taking lo = 2 and not 1;

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());

Since L is the length of major block .So M would always be smaller than L?@Pawel Kacprzak

@pkacprzak @utkarsh_96 @chandyshot

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?.

best editorial

1 Like

Can any one give me the detailed solution for (EIUASSEMBLY - Assembly line) problem in spoj.Link-SPOJ.com - Problem EIUASSEMBLY

can you explain how and why it works?What is the use of big number