PROBLEM LINK:Author: Ke Bi DIFFICULTY:MediumHard 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 $(cc_i)$ guarantees $(ll_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:
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:TermsA 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 insightsWe 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: $$G(n) = \bigcap\limits_{\text{$\vec{d}$ is a decomposition of $n$}} V(\vec{d})$$ 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:
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 answerUnfortunately, 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:
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}$.
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{1933}{10} = 19$ such that $k1$ 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 $k1$ 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$, $Mm_i$ guarantees $Ll_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)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 May '16, 23:43

Thanks for this great problem, maybe better suited for GCJ finals than an ordinary CookOff, but anyway, very nice, requiring a lot of thought and not that much code. Any ideas for the real complexity? And what does $\tilde{O}(1)$ mean? answered 01 Jul '16, 23:54
$f(n) = \tilde{O}(g(n))$ means $f(n) = O(g(n) \log^k n)$ for some $k$. It's a great way to discuss complexity without caring about log factors. In this case, depending on the implementation, the log factors are negligent. This is called softO.
(02 Jul '16, 19:40)
As for the exact complexity, it's quite tricky, and I don't know if my idea is 100% correct, but I have an intuition that at every level of recursion, there are at most $64$ distinct recursive calls. Therefore, the algorithm might actually just be $O(64 \log_{10} n) = O(\log n)$. But since I haven't proven this rigorously yet, I just wrote $\tilde{O}(1)$ just to be safe :)
(02 Jul '16, 19:40)
