skpro19's blog

By skpro19, history, 3 weeks ago, In English,

The problem is this.

The editorial says this:-

We need some observation: There exists an optimal solution such that: in any pile, the box on the higher position will have a smaller strength.

Let k be the minimal number of piles, then there exists an optimal solution such that: The height of all piles is n/k or n/k+1 (if n%k=0, then all of them have the height n/k).

We can prove them by exchange argument: from an optimal solution, swap the boxes in it to make above property holds, and we can ensure it will remain valid while swapping. Then for a given k, we can check whether there exist a solution: the i-th (indexed from 0) smallest strength needs to be at least i/k. So we can do binary search (or just enumerate, since n is only 100) on k.

Doubt:

Why does the ith index need to be atleast i /k ?

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I also like to know the solution, I ask myself the question.