Help with problem BOOKS1 — Copying Books

general
,
#1

Please go through the problem BOOKS1 Spoj. I figured out the following things and reached a state where I require your help:-

  1. I applied binary search over interval [max_element , sum_of_all_elements].
  2. then I calculate x = [lo + hi]/2 ;
  3. I check if I can partition the array in less than or equal to m parts such that no parts’ sum is greater than x;
  4. If I successfully completed this task I reduce hi to x and carry on;
    The problem I face is there can be a case where I might not need exact k partitions (less than k might do) and output format such that first scriber’s work is least.

How do I go further?someone please help me.

#2

If you need less than k partitions then you have to spread out the partitions so as to get exactly k partitions. Let’s take the sample input “5 4 | 100 100 100 100 100” as example. Your final value of x should be 200. That would give 3 partitions [ 100 100 / 100 100 / 100 ]. The problem of stretching that to k partitions and assigning work according to position comes up only before printing, and the search algorithm is not affected by this. Let’s tackle the two problems.

  1. While counting partitions you were probably greedily adding up from the first. Simply working from the opposite end would give us [ 100 / 100 100 / 100 100 ]. As you see the scholars at the end get to do more work. This is an indication that we should work from the end and not the beginning.
  2. Consider we are greedily accumulating the values from the end. When we greedily pick up the 100 at position 2 into our partition 2, that is where we make a mistake, because now the number of values not yet collected is less than the number of partitions left. This is what we have to have to avoid. Just prematurely close a partition when you see that accepting another number will lead to more partitions left than values.
    That’s it. Implement these and it should get AC. Let me know if it works :smiley:
3 Likes
#3

I am facing troubles implementing this . It’s giving wrong answer to the case:

  • 1 5 4
  • 1 1 1 1 1

but correct with

  • 1 9 3
  • 1 2 3 4 5 6 7 8 9

Please help me with the code @meooow.

code link

#4

I think you overlooked the line “The problem of stretching that to k partitions and assigning work according to position comes up only before printing, and the search algorithm is not affected by this”. So the special partitioning is to be done only after getting the answer by binary search. I have modified your code [here][1], take a look. The printing I have left to you.
[1]: http://ideone.com/q4PJZg

1 Like
#5

That was very helpful @meooow. I got it AC. Thank you very much. you are awesome…

#6

I sometimes get confused whether it should be lo<hi or lo<=hi and how to move ranges like hi = mid - 1 ; or hi = mid, sometimes it gets into infinte loop or does not reach a given value. How do you make sure you have written correct binary search… @meooow

#7

Nice work bro!

1 Like
#8

for lo<=hi or lo<hi depends upon your algorithm you are implying inside the while loop! There is no way to calculate before applying this. you can also get AC by taking into consideration of lo<=hi, but in this you have to make changes inside the code!

1 Like
#9

@hulk_baba it depends on the algorithm as @bansal1232 said, but it will be either the lower_bound (as in this one) or the upper_bound that’s required, so doing a few problems like this should make you familiar with the method. Usually I get confused so I have to reason with myself like "if partitions is more than k that means my mid is lower than needed, so I have to definitely increase my mid…lo=mid+1" and "if I have found k partitions that means I should keep trying to minimize mid, but mid itself might be the lowest answer, so hi=mid and not hi=mid-1".
In the end it works :stuck_out_tongue:

1 Like