Proof of Correctness of Codeforces Problem: Fox and Box Accumulation (388A)

Question

I have been trying to solve this problem from the A2OJ 2C Ladder: Fox and Box Accumulation:

Fox Ciel has n boxes in her room. They have the same size and weight, but they might have different strength. The i ^th box can hold at most x_i boxes on its top (we'll call x_i the strength of the box).

Since all the boxes have the same size, Ciel cannot put more than one box directly on the top of some box. For example, imagine Ciel has three boxes: the first has strength 2, the second has strength 1 and the third has strength 1. She cannot put the second and the third box simultaneously directly on the top of the first one. But she can put the second box directly on the top of the first one, and then the third box directly on the top of the second one. We will call such a construction of boxes a pile.

Fox Ciel wants to construct piles from all the boxes. Each pile will contain some boxes from top to bottom, and there cannot be more than x_i boxes on the top of i ^th box. What is the minimal number of piles she needs to construct?

Input

The first line contains an integer n (1 ≤ n ≤ 100). The next line contains n integers x₁, x₂, ..., x_n (0 ≤ x_i ≤ 100).

Output

Output a single integer — the minimal possible number of piles.

I have a greedy solution but I cannot prove it rigorously. That's why I need you folks' help!

My algorithm is as follows (which is quite intuitive):

1. Sort the input_array.

2. Initialize an array called pile_array.

3. Start constructing piles from the top-down, that is, lowest strength first. I select the lowest strength box in the input_array and then delete it from the input_array and add it to the pile_array.

4. I then check for the next lowest strength block from the remaining elements in the input_array after deletion of the element in step 3, and see whether it can be added to the pile_array to make a valid pile or not. If it can, do it. Otherwise continue. (The element chosen in this step may possibly of course have strength equal to that of the last element added to the pile_array.)

5. I then repeat step 3 for that element, that is, add the element in pile_array and delete it from the input_array.

6. After we can no more fill the pile_array, I increase a counter I have preinitialized by 1. I then clear the pile_array (so that I can reuse it).

7. This procedure is repeated for all the remaining elements of the input array.

8. I then output answer as the counter.

The implementation has O(n^2) complexity.

Now to the main problem: I can't prove my algorithm gives the optimal-sized solution. I have tried the following approaches:

1. Prove by swapping that any optimal solution can be converted into the above constructed greedy solution. Failed because I could not get any useful structure in non-greedy solutions....

2. Prove by "greedy always stays ahead" method: My main idea so far is that any optimal solution which is not exactly the same has less than maximum "usage of strength/capacity" of all the blocks. But I am not able to formalize my argument.

I would LOVE to have someone give me a hint to the proof of the algorithm. Please help because I cannot carry on with my life until I prove this problem because of OCD :(.

Just a quick comment: I just checked that the same algorithm was implemented by Legendary Grandmaster tourist (Gennady Korotkevich) during contest time. I also implemented the above algorithm just now and got an Accepted. So rest assured, this algorithm is correct.