CSES - Coin Combinations II

Authors: Michael Cao, Nathan Gong

Table of Contents

SolutionImplementation

Unoffical Editorial (C++)

Note

The solution for this problem is very similar to that of Coin Combinations I. If you haven't solved that already, we recommend doing so before attempting this problem.

The key difference between this problem and Coin Combinations I is that we're now trying to find the number of ordered ways to add the coins to xx. This means that if we had coins {1,3,5}\{1, 3, 5\} and x=4x=4, adding 1+31 + 3 is treated as the same "way" as 3+13 + 1.

Solution

We'll let dp[w]\texttt{dp}[w] equal the number of ordered ways to add the coins up to ww. In the previous problem, we tried out each coin for each possible ww. Here, we'll do the reverse, looping through all possible ww (0wx0\leq w \leq x) for each coin ii while updating dp\texttt{dp} as follows:

dp[w]:=dp[w]+dp[wcoins[i]]\texttt{dp}[w] := \texttt{dp}[w] + \texttt{dp}[w-\texttt{coins}[i]]

This essentially entails switching the order of the nested loops from the previous problem. Since we now loop over the coins before the weights, we only go through the set of coins once, so it's impossible to create two combinations with the same set of coins ordered differently.

Implementation

Time Complexity: O(nx)\mathcal{O}(n \cdot x)

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first

Java

import java.util.*;
public class CoinCombinations2 {
static final int MOD = 1000000007;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int x = sc.nextInt();
int[] coins = new int[n];

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!