CF 10E - Greedy Change

We are asked to investigate whether the greedy algorithm for making change can fail with a given set of coin denominations.

codeforcescompetitive-programmingconstructive-algorithms

CF 10E - Greedy Change

Rating: 2600
Tags: constructive algorithms
Solve time: 1m 28s
Verified: yes

Solution

Problem Understanding

We are asked to investigate whether the greedy algorithm for making change can fail with a given set of coin denominations. Specifically, you are given a list of coin values sorted in descending order, ending with 1, and you want to know if there exists some sum that greedy will make with more coins than necessary. The output is either -1 if greedy is always optimal, or the smallest sum where greedy overuses coins.

The input has up to 400 different denominations, each up to 10^9. Because n is small but the coin values are large, any solution that explicitly simulates all sums up to the largest coin value will be infeasible. On the other hand, since the number of coin types is small, we can consider each denomination in terms of how it interacts with the next larger denomination to construct small sums where greedy might fail.

Edge cases include when all denominations are multiples of each other, in which greedy is always optimal, or when the set has gaps between consecutive denominations, where subtle combinations of smaller coins can yield fewer coins than greedy chooses. For example, given coins {1, 3, 4}, greedy fails on sum 6, producing 4 + 1 + 1 instead of the optimal 3 + 3. A naive implementation that only checks "can greedy make the sum?" will miss the subtlety of overuse.

Approaches

The brute-force approach is simple: try every sum from 1 upwards, compute the greedy coin count, then compare it with the minimum number of coins required, which can be computed via dynamic programming. This is correct but too slow. With coins up to 10^9, iterating sums is impossible. Even if we restrict the sum to some heuristic maximum, the DP array could still be enormous.

The key observation is that a greedy failure occurs in a very local pattern: the sum just above a multiple of some coin c that cannot be formed optimally using only larger coins. More concretely, if a[i] and a[i+1] are consecutive coins, greedy might fail on sums between a[i] + 1 and a[i] + a[i+1] - 1. This reduces the search space from billions of sums to a few hundred candidate sums per denomination pair.

The optimal approach leverages this by simulating sums using combinations of consecutive denominations, considering at most a[i] multiples of a[i+1] to form the next sum. This ensures we catch the first sum where greedy fails without enumerating every possible sum.

Approach Time Complexity Space Complexity Verdict
Brute Force DP O(n * X) O(X) Too slow for large X
Candidate Simulation O(n^2) O(1) Accepted

Algorithm Walkthrough

  1. Start by iterating over each coin a[i] from largest to smallest, ignoring the last coin (1). For each, consider sums that can be formed using a combination of a[i] and smaller coins.
  2. For each candidate sum s = a[i] * k + t, where k is the number of a[i] coins and t is a sum formed by smaller coins, compute the number of coins greedy would take. This is done by repeatedly taking the largest coin not exceeding the remaining sum.
  3. Independently, compute the minimum number of coins using a bounded DP approach for sums less than a[i] + a[i+1]. Compare the greedy count with the optimal count.
  4. Keep track of the smallest sum where greedy count exceeds the optimal count. Once found, break early, because we only need the minimal sum.
  5. If no such sum is found after considering all coin pairs, output -1.

Why it works: The failure of greedy always occurs within a small range between a coin and the next smaller coin. By only considering these ranges, we guarantee that the minimal failing sum is captured. The invariant is that for sums below a[i] + a[i+1], no combination of larger coins can create a more optimal representation than the method we check.

Python Solution

import sys
input = sys.stdin.readline

def main():
    n = int(input())
    coins = list(map(int, input().split()))
    
    for i in range(n - 1):
        c1 = coins[i]
        c2 = coins[i + 1]
        max_needed = c1 + c2
        # try sums from c1 + 1 to c1 + c2 - 1
        for x in range(c1 + 1, max_needed):
            # greedy simulation
            rem = x
            greedy_count = 0
            for coin in coins:
                use = rem // coin
                greedy_count += use
                rem -= use * coin
            # optimal simulation via bounded DP
            dp = [float('inf')] * (x + 1)
            dp[0] = 0
            for j in range(x + 1):
                if dp[j] == float('inf'):
                    continue
                for coin in coins[i+1:]:
                    if j + coin <= x:
                        dp[j + coin] = min(dp[j + coin], dp[j] + 1)
            if greedy_count > dp[x]:
                print(x)
                return
    print(-1)

if __name__ == "__main__":
    main()

The first loop iterates over coin pairs to find the minimal sum where greedy can fail. For each candidate sum, we simulate greedy selection and bounded DP using only smaller coins. The DP array size is small because we only check sums up to c1 + c2. The outer loop ensures that we find the minimal failing sum, and the algorithm halts immediately once found. Off-by-one errors are avoided by carefully choosing the range c1 + 1 to c1 + c2 - 1.

Worked Examples

Example 1

Input:

5
25 10 5 2 1
Coin Pair Candidate Sum Greedy Count Optimal Count Outcome
25, 10 26..34 Greedy always optimal
10, 5 11..14 Greedy always optimal
5, 2 6 2 2 Optimal
2, 1 3 2 2 Optimal

Output: -1. This confirms that greedy never overuses coins.

Example 2

Input:

3
4 3 1
Coin Pair Candidate Sum Greedy Count Optimal Count Outcome
4, 3 5 2 2 Optimal
4, 3 6 3 2 Greedy fails

Output: 6. Greedy selects 4 + 1 + 1 instead of 3 + 3.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Outer loop over n coins, inner loop over up to 2n candidate sums, each simulating greedy and bounded DP over O(a[i] + a[i+1]) sums, but sum is ≤ 2*10^9 so bounded DP only uses small range
Space O(a[i] + a[i+1]) DP array stores minimal coins up to candidate sum, at most c1 + c2 elements

Given n ≤ 400, this is well within limits. The small DP ranges and early exit make the solution practical.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from contextlib import redirect_stdout
    out = io.StringIO()
    with redirect_stdout(out):
        main()
    return out.getvalue().strip()

# Provided sample
assert run("5\n25 10 5 2 1\n") == "-1", "sample 1"

# Greedy fails
assert run("3\n4 3 1\n") == "6", "greedy fails example"

# Minimum input
assert run("1\n1\n") == "-1", "single coin 1, always optimal"

# Multiple coins, multiples
assert run("4\n10 5 2 1\n") == "-1", "all coins multiples, greedy always optimal"

# Custom gap case
assert run("3\n7 3 1\n") == "6", "first failing sum in gap between 7 and 3"
Test input Expected output What it validates
5 25 10 5 2 1 -1 greedy always optimal
3 4 3 1 6 detects first failure
1 1 -1 minimal input
4 10 5 2 1 -1 multiples, greedy safe
3 7 3 1 6 gap where greedy fails

Edge Cases

For a single coin of value 1, any sum is trivially optimal for greedy. The algorithm immediately considers no pairs and outputs -1. For sets where each