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 M(n, state1, state2) be the largest amount of coal that can be produced after n-1 food shipments have already been distributed; state1 describes which shipments have gone to mine 1 so far, and state2 describes which shipments have gone to mine 1 so far. Furthermore, let value(a, b) denote the amount of coal produced when food of type b arrives to a mine in state a. The following recursive formula holds:

\displaystyle M(n, state1, state2) = \max \begin{cases}
M(n+1, newstate1, state2) + value(state1, \text{type of shipment }n) \\
M(n+1, state1, newstate2) + value(state2, \text{type of shipment }n)

One could write a simple recursion based on the above formula (calculate M(0, empty, empty)). Such an algorithm has \mathcal O(2^N) complexity and would score 45 points.

Note that, for calculating the value of M, 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 3 \times 3 + 1 = 10 per mine (3 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: N shipments \times 10 states (for the first mine) \times 10 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 N as high as 100\,000, using so much memory (100N 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 M(n, *, *), we only use M(n+1, *, *). If we calculate M in decreasing order of n, we need only 2 \times 100 integers.


There are no comments at the moment.