Google APAC(CodeJam) Tiling Problem

Revision en1, by infomaniac, 2016-10-26 19:53:33

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 ?

Tags codejam, knapsack, greedy, np-hard

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English infomaniac 2016-10-26 19:53:33 612 Initial revision (published)