Greedy Change

Call the system canonical if greedy is always optimal. We need the smallest value $x$ for which greedy is not optimal.

This is one of those problems where brute force is not just slow — it’s mathematically the wrong attack. Coin values go up to $10^9$, so if you don’t exploit structure, you’re toast.

Notation

The coin values are already given in decreasing order: $a_1 > a_2 > \dots > a_n = 1.$

Let:

• $G(x) = (g_1,\dots,g_n)$ be the greedy representation of $x$,
• $\operatorname{gr}(x) = \sum g_i$ be the number of coins greedy uses,
• for any representation $m=(m_1,\dots,m_n)$, $V(m)=\sum_{i=1}^n m_i a_i, \qquad |m|=\sum_{i=1}^n m_i.$

We want the smallest $x$ such that there exists some representation $m$ with $V(m)=x \quad \text{and} \quad |m| < \operatorname{gr}(x).$

The key theorem

The hard part is a classical characterization due to Pearson.

If greedy ever fails, then the smallest counterexample has a very special form. There exist indices $2 \le i \le j \le n$ such that, if $G(a_{i-1}-1)=(g_1,\dots,g_n),$ then an optimal representation of the smallest counterexample is

g_k,&k<j,\\ g_j+1,&k=j,\\ 0,&k>j. \end{cases}$$

In words: take greedy on $a_{i-1}-1$, add one extra coin of denomination $a_j$, and kill the whole smaller tail.

That’s the whole damn trick. Without this theorem, the search space is enormous. With it, only $O(n^2)$ candidates survive.

Why this is believable

A full proof is a bit technical, but the intuition is clean:

• Let $x$ be the smallest bad value.
• Compare greedy and an optimal representation of $x$.
• They must share a prefix on large denominations; otherwise, removing the common prefix gives a smaller bad value, impossible.
• Let $i$ be the first place where optimal stops following greedy.
• After removing the common prefix, the remaining value is $< a_{i-1}$, so the boundary object is exactly $a_{i-1}-1$.
• Now delete one suitable coin from the optimal representation. The remaining sum is smaller than $x$, so greedy must be optimal there. That forces the suffix to be exactly the greedy representation of $a_{i-1}-1$, truncated at some $j$, with one extra $a_j$ coin added.

So the smallest bad value can’t be some random Frankenstein number. It has this rigid shape.

Turning the theorem into an algorithm

For every $i=2..n$:

1. Compute the greedy representation $g = G(a_{i-1}-1).$
2. For every $j=i..n$, build the candidate representation g_k,&k<j,\\ g_j+1,&k=j,\\ 0,&k>j. \end{cases}$$
3. Let $w = V(m), \qquad c = |m|.$
4. Recompute greedy on $w$.
   • If greedy uses more than $c$ coins, then $w$ is a counterexample.
   • Keep the smallest such $w$.

If no candidate works, the system is canonical and the answer is $-1$.

Small optimization

For fixed $i$, once we know $g=G(a_{i-1}-1)$, we don’t need to rebuild each candidate from scratch.

If we sweep $j$ from left to right, maintain: $P_V(j)=\sum_{k=1}^{j} g_k a_k, \qquad P_C(j)=\sum_{k=1}^{j} g_k.$ Then the candidate for this $j$ is simply: $w = P_V(j) + a_j, \qquad c = P_C(j) + 1.$

That makes candidate generation $O(1)$ each after the greedy vector is known.

Example

For coins $[4,3,1]$:

• Take $i=2$, so we look at $a_1-1 = 3$.
• $G(3) = (0,1,0)$.
• Choose $j=2$: $m=(0,2,0), \quad w=6, \quad c=2.$
• Greedy on $6$ gives $4+1+1$, i.e. $3$ coins.

So $6$ is a counterexample, and in fact the smallest one.

Correctness sketch

We check every candidate guaranteed by Pearson’s theorem. Therefore, if a counterexample exists, the smallest one will appear in our enumeration.

For each enumerated candidate $w$, we explicitly have a representation using $c$ coins. If $\operatorname{gr}(w) > c,$ then greedy is not optimal for $w$, so $w$ is indeed a valid counterexample.

Thus:

• if we output some minimum $w$, it is truly a counterexample,
• if we output $-1$, then no Pearson candidate works, hence no counterexample exists at all.

Complexity

There are $O(n^2)$ candidates. For each one, we may recompute greedy in $O(n)$ time. So total complexity is $O(n^3),$ which is perfectly fine for $n \le 400$.

Memory usage is $O(n).$

Short version: the theorem does the heavy lifting, the code just cashes the check.