UVA - 11259 - Coin Changing Again

This article will explain my thought process to solve a problem called Coin Changing Again (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Coin Change, Dynamic Programming, Combinatorics

Objective

Given:

4 coin denominations.
Number of queries.
List of queries.
1. 4 coin quantities.
2. A value.

We want to:

Find total ways to obtain the query’s value by combining the coins up to the query’s quantities.

Glossary

Coin Change (CC) — A classic algorithmic problem that involves finding the minimum number of coins needed to make a certain amount of change.
Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Combinatorics — A branch of mathematics concerned with counting, arranging, and structuring finite sets of objects.
Principle of Inclusion and Exclusion (PIE) — A counting technique in combinatorics that calculates the size of the union of multiple sets.

Observation

This problem is similar to CC problem, as we want to find the total ways to get an amount of value by combining limited quantities of coins with various denominations. However, the classical CC approach using DP is not fast enough to solve the problem. We need to find the total ways for multiple different quantities and value, so we need to ensure that the DP result can be reused across the queries.

To ensure that the DP can be reused across the queries, since the denominations are constant across the queries, we can perform the CC DP with the assumption that the quantities are infinite and the maximum value is 10^5.

After we have the total ways with infinite coins, how do we calculate the total ways with limited coins? This is where combinatorics came into play. From the total ways with infinite coins, we want to exclude the total ways when any of the coin has exceeded the quantity. Lets say we have function W(C), with C being a set of coins that exceeded the quantity and W being a function to get the total ways. Using PIE, we can get the total ways with limited quantities from W() - W(0) - W(1) - W(2) - W(3) + W(0, 1) + W(0, 2) + W(0, 3) + W(1, 2) + W(1, 3) + W(2, 3) - W(0, 1, 2) - W(0, 1, 3) - W(0, 2, 3) - W(1, 2, 3) + W(0, 1, 2, 3).

The next question is, how do we get W(C) from the total ways of infinite coins? Lets start simple from W(0). Lets say we have function DP(V) with V being a value and DP being a function to get the total ways to get the value with infinite coins, D(0) being the denomination of the 0-th coin, and Q(0) being the quantity of the 0-th coin. We can say that we have exceeded the quantity when the 0-th coin has been used Q(0) + 1 times. The interesting part is, we can get the total ways of the exceeding quantity from DP(V - D(0) * (Q(0) + 1). The same mechanism can be applied for the other W(C). Apply this to the PIE equation, and we will get the total ways with the limited coins.

Algorithm

We can implement the CC using DP algorithm. The DP will calculates the number of ways to get a certain value, so it means the computation can be stored in a 1 dimensional array, with the first dimension of the array being the value and the value of the array being the total ways. The DP itself can be implemented with a bottom-up approach. For each coin and each possible value, we can create a new value by adding the coin into the existing value, in which the total ways to get the new value will increases by the amount of the total ways to get the existing value.

For the PIE, since the number of coins is quiet small, we can hardcode the combination of the coins to get the W(C) from the result of the DP.

The time complexity of this solution is O({total coins} * {maximum value}) or O(10^5).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 11259 - Coin Changing Again
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2226
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalTestCases = in.nextInt();
        for (int i = 0; i < totalTestCases; i++) {
            final Input input = new Input();
            input.coins = new int[4];
            for (int j = 0; j < 4; j++) {
                input.coins[j] = in.nextInt();
            }
            input.totalQueries = in.nextInt();
            input.queries = new int[input.totalQueries][5];
            for (int j = 0; j < input.totalQueries; j++) {
                for (int k = 0; k < 5; k++) {
                    input.queries[j][k] = in.nextInt();
                }
            }

            final Output output = process.process(input);
            for (final long answer : output.answers) {
                out.println(answer);
            }
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int[] coins;
    public int totalQueries;
    public int[][] queries;
}

class Output {
    public long[] answers;
}

class Process {
    private static final int MAX_VALUE = 100_000;

    public Output process(final Input input) {
        final Output output = new Output();

        final int[] coins = input.coins;
        final long[] totalWaysPerValue = findTotalWaysPerValue(coins);

        output.answers = new long[input.totalQueries];
        for (int i = 0; i < input.totalQueries; i++) {
            final int[] query = input.queries[i];
            final int[] counts = Arrays.copyOfRange(query, 0, 4);
            final int value = query[4];

            final long totalWays = findTotalWays(totalWaysPerValue, value, coins, counts);
            output.answers[i] = totalWays;
        }

        return output;
    }

    // Coin Change with Dynamic Programming
    private long[] findTotalWaysPerValue(final int[] coins) {
        final long[] totalWaysPerValue = new long[MAX_VALUE + 1];
        totalWaysPerValue[0] = 1;

        for (final int coin : coins) {
            for (int value = 0; value <= MAX_VALUE - coin; value++) {
                final int newValue = value + coin;
                totalWaysPerValue[newValue] += totalWaysPerValue[value];
            }
        }

        return totalWaysPerValue;
    }

    private long findTotalWays(
        final long[] totalWaysPerValue,
        final int value,
        final int[] coins,
        final int[] counts
    ) {
        final long w = getTotalWays(totalWaysPerValue, value, coins, counts);

        final long w0 = getTotalWays(totalWaysPerValue, value, coins, counts, 0);
        final long w1 = getTotalWays(totalWaysPerValue, value, coins, counts, 1);
        final long w2 = getTotalWays(totalWaysPerValue, value, coins, counts, 2);
        final long w3 = getTotalWays(totalWaysPerValue, value, coins, counts, 3);

        final long w01 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 1);
        final long w02 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 2);
        final long w03 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 3);
        final long w12 = getTotalWays(totalWaysPerValue, value, coins, counts, 1, 2);
        final long w13 = getTotalWays(totalWaysPerValue, value, coins, counts, 1, 3);
        final long w23 = getTotalWays(totalWaysPerValue, value, coins, counts, 2, 3);

        final long w012 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 1, 2);
        final long w013 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 1, 3);
        final long w023 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 2, 3);
        final long w123 = getTotalWays(totalWaysPerValue, value, coins, counts, 1, 2, 3);

        final long w0123 = getTotalWays(totalWaysPerValue, value, coins, counts, 0, 1, 2, 3);

        final long totalWays = (
            w
            - w0 - w1 - w2 - w3
            + w01 + w02 + w03 + w12 + w13 + w23
            - w012 - w013 - w023 - w123
            + w0123
        );
        return totalWays;
    }

    private long getTotalWays(
        final long[] totalWaysPerValue,
        final int value,
        final int[] coins,
        final int[] counts,
        final int... excludeIds
    ) {
        int excludeValue = value;
        for (final int excludeId : excludeIds) {
            final int excludeCount = counts[excludeId] + 1;
            final int excludeCoin = coins[excludeId];
            excludeValue -= excludeCount * excludeCoin;
        }

        return getOrDefault(totalWaysPerValue, excludeValue, 0);
    }

    private long getOrDefault(final long[] array, final int index, final int defaultValue) {
        final boolean valid = 0 <= index && index < array.length;
        return valid ? array[index] : defaultValue;
    }
}