Google APAC(CodeJam) Tiling Algorithm

Question

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 Idea, I am unable to understand why this even works optimally here. In particular how can we prove that this algorithm is optimal ?

Problem Statement :

Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants N tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square. The lengths of side of the tiles are 2^S1, 2^S2, ..., 2^SN. He can only buy a lot of tiles sized M*M, and he decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?

Answer 1

The essence of the proposed solution is first fit decreasing (FFD) heuristic.

Let's call sizes of for the Bin Packing problem nesting if for each a_i < a_j, a_i = k_ij a_j. Notice, that according to this definition, the original problem is Nesting Bin Packing problem.

Let's proof that FFD heuristic solves Nesting Bin Packing. Consider a counter-example: non-increasing sequence of item sizes a_i and an optimal solution OPT that is not achieved by FFD heuristics. There is the first i that requires bin number OPT+1. This means, that all previous items was packed and there are no space for item i.

Let's compare the distribution of the first i-1 items using FFD and optimal distribution of i items. The total size of placed items in optimal distribution are higher by a_i. So, for at least one bin, the total size of items in optimal distribution is greater than in FFD distribution. Due to nesting, all items considered so far, may be split in some number of a_i-sized items, so both totals are multiples of a_i, and the minimal possible difference between them is a_i. Therefore, we found a bin for item i, that leads to contradiction.

The contradiction is clear in the 1D case (original Bin Packing problem), but no so clear for 2D case. Let’s introduce a grid with cell size A=√a_i and the origin in the top-left corner. Side length of already placed title will be multiples of A. We’ll shift all titles in both solutions to the top (in order from top to bottom), then, to the left (in order from left to right). After that all tiles will have integer coordinates on the grid. But there are more occupied cells in optimal solution than the FFD one, so there are should be at least one A×A cell that is occupied in optimal solution, and is free in the FFD one. Let’s use it to place tile i.