Editorial for IOI '07 P4 - Miners

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The problem is solved using dynamic programming. Let be the largest amount of coal that can be produced after food shipments have already been distributed; describes which shipments have gone to mine 1 so far, and describes which shipments have gone to mine 1 so far. Furthermore, let denote the amount of coal produced when food of type arrives to a mine in state . The following recursive formula holds:

One could write a simple recursion based on the above formula (calculate ). Such an algorithm has complexity and would score 45 points.

Note that, for calculating the value of , it suffices to describe the state of a mine by the last two shipments only. This is because any shipment, other than the last two, cannot influence the amount of coal produced. The total number of different states is thus reduced to only per mine ( types of food in each of the last two shipments, and a special state describing an empty mine).

This allows us to drastically reduce the total number of configurations: shipments states (for the first mine) states (for the second mine). For each of the configurations, we can calculate the value of the configuration once and store it for reuse.

However, with as high as , using so much memory ( integers) for storing the values of the configurations would exceed the memory limit and score between 70 and 85 points.

To get the full score, we note that, when calculating , we only use . If we calculate in decreasing order of , we need only integers.