PROBLEM LINKS
DIFFICULTY
MEDIUM-HARD
PREREQUISITES
Greedy
PROBLEM
We have N retort pouches of food. The i-th pouch contains Vi units of food and expires on the Ui-th day. Once we open the i-th pouch, we can only consume the food within Li days. In the other words, if we open the i-th pouch on the xi-th day, we can only consume the food on the k-th day, where xi ≤ k ≤ min(Ui, xi + Li - 1).
Each day, we can consume at most two units of food. Of course, we might not be able to consume all units and some units must be discarded. Determine the minimum number of discarded units.
There is also a restriction that once you open some pouch, food units from previously opened pouches should be discarded.
This is a major clarification to the problem statement that was made after the contest. We are extremely sorry about that. We all have missed the possibility to achieve better score without this restriction in some situations. We are grateful to Mikhail Kever for pointed out our mistake (see his answer).
EXPLANATION
When to open the pouches
Since there is a restriction of the maximum time between opening each pouch and consuming units from it, it is always optimal to open each pouch on the first time we consume a unit from it.
Maximum number of units than can be consumed
Consider the i-th pouch. How many units of food can we consume from it, ignoring the use-by date? Because we can only eat at most two units every day, the maximum number of unit is of course 2 × Li. So, for each i, if Vi > 2 × Li, we can safely set Vi = 2 × Li.
Categorizing the pouches
Due to the clarification to problem statement above units from a pouch should be consumed consecutively. Based on this, we can categorize the pouches into 3 types:
Type 1: Vi is odd. We call this pouch an odd pouch. To consume all units optimally, there are two patterns:
- 1+2+2+...+2+2
- 2+2+...+2+2+1
Type 2: Vi is even and Vi < 2 × Li. We call this pouch an even pouch. To consume all units optimally, there are two patterns:
- 2+2+...+2+2
- 1+2+2+...+2+2+1
Type 3: Vi = 2 × Li. We call this pouch a bad pouch. To consume all units optimally, there are only one pattern:
- 2+2+...+2+2
Why must we have an additional bad pouch category here? It is important when we open a pouch on a certain day, and at the same time we have already consumed a unit from another pouch. In this case, we cannot consume all units if it is a bad pouch, whereas can consume all units from the other two types of pouches (assuming the use-by date is still far away).
Choosing the order of consumption
Now that we know how to consume the pouches, we will greedily choose which pouches to consume. Let’s work backwards: we reverse time and consume the pouches in backwards direction. We will try to consume the pouches as late as possible.
When we decide to consume a certain pouch, it is always possible to consume as many units as possible from this pouch. Why? Because all units are unweighted, if at some day (in backwards direction) we stop consuming and start consuming another pouch, and we still has remaining units from the current pouch, it is always safe to replace the units from the other pouch with the ones from the current pouch, without breaking the use-by date or maximum distance restriction from the other pouch.
Let’s maintain 2 values during the consumption:
- D: the latest day on which we can consume at least one unit. At first we set D = infinity, and we will decrease D as we consume units.
- E: the number of units we have already consumed on the D-th day.
We will try consuming units as long as D is positive as there is at least one pouch that has not been consumed yet. At each step in the iteration, there are 2 cases:
Case 1: D ≤ max{Ui : pouch i has not been consumed}. Here we can consume pouch i starting on the D-th day backwards if D ≤ Ui. To maximize the number of consumed units, we want that on the last day (backwards) we consume 2 units from this pouch, if this is possible. In other words, we want that the next pouch we consume has the same parity as E. So, there are two possibilities:
- E = 0. Choose a bad or even pouch that satisfies D ≤ Ui. If there is no such pouch, choose an odd pouch that satisfies D ≤ Ui. Then consume min(2 × D, Vi) units from it.
- E = 1. Try the pouches in this order: odd, even, bad. Take the first type that has a pouch which satisfies D ≤ Ui.
Note that when E = 0 for even and bad pouch, we can choose any pouch which satisfies D ≤ Ui, because if there is more than one such pouch, we can consume all of them in any order (if there is sufficient time). However this is not true for odd pouch. We should pick odd pouch with largest Vi, among available pouches.
Refer to this example
5 7 13 4 7 12 4 4 6 2 5 12 3 3 2 2
The optimal way is to consume pouches in the provided order and we will eat all food then. But if someone will use 4th pouch instead of 2nd one at first then one food unit will be discarded.
But thanks to the constraint “If Vi < Vj then Ui ≤ Uj”, we can just sort each type of pouches in non-increasing order of (Ui, Vi) and at each iteration we can pick the pouch with the largest Ui for each type. That will guarantee we pick the pouch with largest Vi in O(1) time, when we have only odd pouches.
Now, when E = 1, we have a problem. If we can take an odd or even pouch, we can always consume min(2 × D - 1, Vi) units from it. If there are only bad pouches available, there are two options:
- Consume min(2 × D - 1, 2 × Li - 1) units starting from day D, and remove min(D, Li - 1) days, or
- Consume min(2 × D - 1, 2 × Li) units starting from day D - 1 (i.e. 1 unit on day D and 2 units on the remaining days), and remove min(D, Li) days.
Which option to choose? It seems that it is non-trivial to decide which option is better. So, let’s just test! First, save all current state variables (D, E, consumed pouches) and just choose the first option (i.e. consuming all units but one from this bad pouch). And then we proceed according to the above greedy logic with small exception is that if we again meat this trouble case we choose the first option with eating only min(2 × D - 1, 2 × Li - 1) units of food without saving any previous states.
If at some time we ever meet Case 2 (will be explained below), then we will have some free days and actually it is better to choose the second option. So in this case we cancel our decision and choose second option and then start over again from this state.
On the other hand if we never meat Case 2 it would mean that we eat exactly 2 units of food each day from 1 to D so our choice was indeed optimal (that is why we always choose the first option in trouble situation during this test).
Case 2: D > max{Ui : pouch i has not been consumed}. Here, we have D - max{Ui} free days on which we cannot consume any units. If we meet this case during the test in Case 1 as mentioned above, we can cancel our previous decision. Otherwise, let’s set D = max{Ui} and continue our iteration at Case 1.
After consuming some units from a pouch, do not forget to update D and E as well.
We can sort the pouches of each type in non-increasing order beforehand so that the pouch with Ui ≥ D in each step in the iteration can be retrieved in O(1) time (just pick the largest Ui).
The total time complexity of this solution is O(N^2) because of the test in Case 1.
Please consult setter/tester’s solution for more reference.
AUTHOR’S AND TESTER’S SOLUTIONS
Author’s solution can be found here.
Tester’s solution can be found here.
