PROBLEM LINK:
Author: Ke Bi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Recursion, dynamic programming
PROBLEM:
The denominations of euro coins are 1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 50000. Given C which is one of these values, and L \in [1,C], what is the maximum value C' \le C such that in every possible decomposition of C' into euro coins, you can pay exactly L euros?
QUICK EXPLANATION:
We say that c guarantees l if in every possible decomposition of c into euro coins, you can pay exactly l euros.
Given c, l, and a list of integer pairs P = [(c_1,l_1),(c_2,l_2),\ldots,(c_k,l_k)], let F(c,l,P) be the maximum c' \le c such that (c-c_i) guarantees (l-l_i) for every i. The answer that we want is F(C,L,[(0,0)]).
There are only fourteen important compositions of coins [1,2,5] that we need to consider:
- [],
- [1],
- [5,2,2,2],
- [2],
- [1,2],
- [5,2,2,2,2],
- [2,2],
- [5],
- [2,2,2],
- [1,5],
- [5,2],
- [2,2,2,2],
- [1,5,2],
- [5,2,2].
Everything else is divisible by 10. With the help of this fact, we can compute F(c,l,P) recursively using at most 10 recursive calls, and in fact many such calls overlap, so memoizing will help too. The details of the recursion will be discussed below.
EXPLANATION:
Terms
A coin collection is a multiset of integers where each integer is a valid euro denomination. For example \{5,5,10\} is a coin collection. To denote coin collections using variables, we’ll use variables with arrows on top, e.g. \vec{d}.
A coin collection \vec{d} is a decomposition of an integer n if the sum of the coins in \vec{d} is n. For example \{5,5,10\} is a decomposition of 20.
The value set of a coin collection \vec{d}, denoted V(\vec{d}), is the set of values which you can pay with this coin collection. For example, V(\{5,5,10\}) = \{0,5,10,15,20\} because you can pay 5, 10, 15 and 20 with the coins \{5,5,10\}.
We say that an integer n guarantees an integer k if you can pay for k euros regardless of how n is decomposed. In other words, n guarantees k if k is in the value set of every decomposition of n. For example, 3 guarantees 1 because 1 is both in V(\{1,2\}) and V(\{1,1,1\}), but 4 doesn’t guarantee 1 because it’s not in V(\{2,2\}).
The guarantee set of an integer n, denoted G(n), is the set of values that n guarantees. For example, G(4) = \{0,2,4\}, and G(8) = \{0,2,6,8\}.
Some insights
We can now translate the problem as: Given C and L, what is the largest value \le C that guarantees L? For a given C and L, let’s denote the answer by F(C,L).
The most naĂŻve way to solve this is to loop downwards starting from C, and find the first one whose guarantee set contains L.
To compute the guarantee set, a very useful relationship between G(n) and V(\vec{d}) is the following:
Computing V(\vec{d}) for a given \vec{d} can be done with the usual dynamic programming approach that runs in O(\operatorname{length}(\vec{d})\cdot \operatorname{sum}(\vec{d})). (See this.)
Unfortunately, each n has a lot of decompositions, so computing G(n) is very slow. One way to speed up the computation is to notice that some value sets completely contain other value sets. For example, V(\{1,1,1,5,10\}) completely contains V(\{1,2,5,10\}), because whatever value you form with \{1,2,5,10\}, you can also form with \{1,1,1,5,10\} by replacing the 2 with 1+1. Thus, in the context of computing G(n) with the above formula, we don’t really need to compute V(\{1,1,1,5,10\}). Another example: V(\{1,2,2,5,20\}) completely contains V(\{10,20\}), because 1+2+2+5 = 10.
Extending this, it means that we don’t need to check some value set if we can show that it completely contains another value set. Here are some simple cases where this is true:
- Some coin in \{1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000\} appears twice.
- Some coin in \{2, 20, 200, 2000, 20000\} appears five times.
- One of the following subsets appear: \{1,2,2\}, \{10,20,20\}, \{100,200,200\}, \{1000,2000,2000\}, \{10000,20000,20000\}.
By only considering decompositions of n where all the above are false, the number of decompositions drastically decreases, and it makes computing G(n) much, much faster! (The maximum number of decompositions you need to check reduces to 16.)
Computing the answer
Unfortunately, computing F(C,L) naĂŻvely is still too slow even if we can compute G(n) quickly for a given n.
One important observation is that the number of selections for the coins 1, 2 and 5 are very limited. In fact, there are only 14 of them:
- \{\},
- \{1\},
- \{5,2,2,2\},
- \{2\},
- \{1,2\},
- \{5,2,2,2,2\},
- \{2,2\},
- \{5\},
- \{2,2,2\},
- \{1,5\},
- \{5,2\},
- \{2,2,2,2\},
- \{1,5,2\},
- \{5,2,2\}.
All other selections will violate one of the three conditions we described above. Also, the remaining coins are all divisible by 10! What’s more, dividing all the other coins by 10 will give us the same set of coins as the original! (Minus of course the large ones: 10000, 20000, 50000.)
This hints to us that a recursive function that somehow divides the arguments by 10 is possible.
Let’s illustrate that with an example. Suppose we are computing F(200,51), and that we know that the answer is \equiv 3 \pmod{10}. Thus, we’re finding the maximum value M \le 193 of the form M = 10k+3 that guarantees 51. Then because M \equiv 3 \pmod{10}, there are only two possibilities for the small coins in the decomposition of M: \{5,2,2,2,2\} and \{1,2\}. For M to guarantee 51, some conditions must hold. Note that 51 \equiv 1 \pmod{10}.
- If the coin selection is \{5,2,2,2,2\}, then the only way to form a sum \equiv 1 \pmod{10}, is when we select the coin set \{5,2,2,2\}. Every other coin is then divisible by 10, and their sum must be equal to 51-(5+2+2+2) = 40. This means that \frac{M-(5+2+2+2+2)}{10} = k-1 guarantees the value \frac{40}{10} = 4.
- If the coin selection is \{1,2\}, then the only way to form a sum \equiv 1 \pmod{10}, is when we select the coin set \{1\}. Every other coin is then divisible by 10, and their sum must be equal to 51 - (1) = 50. This means that \frac{M-(1+2)}{10} = k guarantees the value \frac{50}{10} = 5.
In other words, if we know that the answer is \equiv 3 \pmod{10}, then the answer is the number 10k+3, where k is the largest number \le \frac{193-3}{10} = 19 such that k-1 guarantees 4 and k guarantees 5. This is where the division by 10 comes in!
Now, finding this k is a whole different procedure, and we can’t simply recurse to using the function F(C,L) again, because we need k to guarantee 5 and also k-1 to guarantee 4 at the same time. But we can easily fix this by generalizing F(C,L): We define a new function F'(C,L,P), where P is a list of integer pairs P = [(m_1,l_1),(m_2,l_2),\ldots,(m_t,l_t)], and F'(C,L,P) is defined as the maximum M \le C such that for every (m_i,l_i) \in P, M-m_i guarantees L-l_i. The original function F(C,L) is then equivalent to F'(C,L,[(0,0)]).
To compute F'(C,L,P), a generalization of the above idea works. But that assumes you know the value of the answer mod 10. No problem! Just try every possible value mod 10, and get the maximum among them! This gives us at most 10 recursive calls, but in fact, many of these recursive calls overlap, which means memoization will greatly help!
That’s the general idea of the solution. Lots of small details weren’t described in the editorial, so for those, you can check out my implementation below. (See the tester’s solution.)
Time Complexity:
\tilde{O}(1)
