[HELP NEEDED] Why does these solutions for CSES Coin Combination 1 & 2 work ?

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

To brush up on my DP skills I decided to solve some problems from the topic from CSES.

I came across 2 problems of very similar solutions: Coin Combinations I and Coin Combinations II.

In the first problem, the order of the coins matter and in the second version, it does not.

Code for 1st problem

{
    int n, x;
    cin >> n >> x;
    vector<int> c(n);
    forn(i, n)
    {
        cin >> c[i];
    }
    sort(all(c));
    vector<int> dp(x + 1, 0);
    dp[0] = 1;
    for (int j = 0; j <= x; j++)
    {
        for (int i = 0; i < n && c[i] <= j; i++)
        {
            dp[j] += dp[j - c[i]];
            dp[j] %= MOD;
        }
    }
    cout << dp[x] << "\n";
}

Code for 2nd Problem

void solve()
{
    int n, x;
    cin >> n >> x;
    vector<int> c(n);
    forn(i, n)
    {
        cin >> c[i];
    }
    sort(all(c));
    vector<int> dp(x + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= x; j++)
        {
            if (c[i] <= j)
            {
                dp[j] += dp[j - c[i]];
                dp[j] %= MOD;
            }
        }
    }
    cout << dp[x] << "\n";
}

What's interesting is that both these solutions are basically the same, the only difference being the order of the for loops reversed. This is where I am confused. I tried to run a few test cases by hand and managed to understand how this code works but I can't figure out why this code works the way it does.

I have a very foggy intuition about the 2nd one, wherein I am visualizing how every coin $$$c_i$$$ contributes to a particular sum (much like the sieve algorithms), But I may be wrong.

Any Help would be greatly appreciated :).

Comments (2)

Show archived | Write comment?

Perry_Prasad_Platypus

4 years ago, # |

You can see that in the solution of Coin Combination II, we are always using the coins with least value first. When you were starting the j loop in that solution, we were in some way assuming that we have only one coin of value 0. Now, when we have processed for j=0 and are starting processing for j=1 we can see that it's similar to the starting of loop j=0 with only difference that we have already a coin of value 0, c[0] ,2*c[0], 3*c[0].... and we are only using one of these at a time. The whole conclusion is to give you the intuition that in the second solution all coins of similar types are always used together and coins are used in ascending order of values so it is just like sorting the values used for forming x and then calculating the number of different ways. While in first solution the last used coin can be anything. So we can have any order of the coins. Hope it was useful.

→ Reply

Rainman84

4 years ago, # ^ |

Thanks Perry_Prasad_Platypus, this has given me a better insight to the problem.

Rainman84's blog