Tags: competitive-programming, math
This article was translated from my Japanese blog.
2069 Greedy, Greedy
Problem
You are given n coin denominations c1, …, cn. First, determine whether there are amounts that cannot be paid exactly with these coins. If every amount can be paid exactly, determine whether there is an amount for which the greedy method is not optimal, which means the greedy method cannot find the optimal solution for the coin exchange problem. (1 ≤ n ≤ 50, 0 < c1 < … < cn < 1000)
Solution
It can be proven by induction that “there is an amount that cannot be paid exactly with the given coins” ⇔ “there is an amount between 1, 2, …, cn that cannot be paid exactly with the given coins”. Therefore, we can determine this by iterating over 1, …, cn in O(cn).
If every amount can be paid exactly, we need to check whether there is an amount for which the greedy method fails to find the optimal solution. However, by the following fact, it is enough to compare the greedy solution with the optimal solution for each amount from 1 to 2cn.
The minimum amount a for which the greedy solution is not optimal is at most 2cn; that is, a ≤ 2cn.
For simplicity, define the following notation: $$ \begin{align} a &:= \text{the minimum of all amounts for which the greedy solution is not optimal}, \\ opt(x) &:= \text{the optimal solution for }x, \\ grd(x) &:= \text{the greedy solution for }x. \end{align} $$ Assume a > 2cn. By definition, opt(a) < grd(a).
Since cn < a − cn < a, $$ \begin{aligned} grd(a) &= grd(a - c_n) + 1 = opt(a - c_n) + 1. \end{aligned} $$
Also, since cn < a − cn < a − ci < a for all ci, by the definition of opt, $$ \begin{aligned} opt(a) &= \min_{i = 1, \dots, n}\{opt(a - c_i) + 1\} \\ &=\min_{i = 1, \dots, n}\{grd(a - c_i) + 1\} \\ &=\min_{i = 1, \dots, n}\{grd(a - c_i - c_n) + 2\} \\ &=\min_{i = 1, \dots, n}\{opt(a - c_n - c_i) + 1\} + 1 \\ &= opt(a - c_n) + 1 \\ &= grd(a). \end{aligned} $$ This is a contradiction. Thus, a ≤ 2cn.
The greedy solution can be calculated in O(n), and the optimal solution can be precomputed with dynamic programming in O(n ⋅ 2cn). Therefore, the total runtime complexity is O(ncn).