SCHEDULE - Editorial

editorial
, , , ,
41

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

42

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

43

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 .

44

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

45

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

1 Like
46

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

47

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

48

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

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

50

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

51

For a block like 0000000 and flips = 3, 0101010. I think its 0 based, provided u store it similarly.

52

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

53

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.

54

@vijju123

look at the first three lines of last paragraph and then read my previous comment once again.

55

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.

56

@vijju123

Okay, I will check that out.

57

best editorial

1 Like
58

Can any one give me the detailed solution for (EIUASSEMBLY - Assembly line) problem in spoj.Link-http://www.spoj.com/problems/EIUASSEMBLY/