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

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	adamant	156
4	maroonrk	153
5	-is-this-fft-	148
5	SecondThread	148
5	atcoder_official	148
8	Petr	147
9	nor	144
9	TheScrasse	144

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

3 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

3 years ago, # ^ |

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

Rainman84's blog