infomaniac's blog

By infomaniac, history, 6 years ago, In English

I am stuck at the following question Problem Statement. I have thought about this for some time and then looked at some clues for the problem because I could not come up with a solution. My understanding is that this is a special case of "Bin Packing" problems which in general are NP-Hard. Looking at this idea in particular CodeForces Blog, I am unable to understand why this even works optimally here. In particular how can we prove that this algorithm is optimal ?

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