@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
the binary search logic:
maxL = 1e6
minL = 1
m = (maxL + minL)/2
now calculate the number of bits need to change/flip to have m as the answer.
if the count is less than k less then the answer can be less than m(even lower than m, so maxl =m ) else m cannot be the answer so answer lies in between m and maxL(minl=m).
in the end minl is the answer
it is simple greedy technique.The longest segment stays on the top of the priority queue, we pop it and divide it by the required factor.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.Hence initially we select a big number in the priority queue.
DEVSTR
https://discuss.codechef.com/questions/69954/devstr-editorial
It’s practically the same almost.
2 Likes
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.
no code there…
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.
and how we will know about a ?
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 .