CSES - Coin Combinations II

Author: Michael Cao

This editorial assumes that you've solved Coin Combinations I (which is very similar). If not, the editorial can be found here. For this problem, we'll use the same state and transitions.

Dealing with Ordered Ways

To only count ordered ways, we switch the order of the loops. Since we loop over the coins before the weights in the dp array, it's impossible to create two combinations with the same coins ordered differently, because the order that we update the weights using the coins is the order we loop over them.

1#include <bits/stdc++.h>
2using namespace std;
3using ll = long long;
4using vi = vector<int>;
5#define pb push_back
6#define rsz resize
7#define all(x) begin(x), end(x)
8#define sz(x) (int)(x).size()
9using pi = pair<int,int>;
10#define f first

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!

Give Us Feedback on CSES - Coin Combinations II!