Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

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

Revision en2, by Rainman84, 2021-05-24 07:28:48

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
Code for 2nd Problem

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 :).

Tags #dynamic programing, #cses

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Rainman84 2021-05-24 07:28:48 1083 (published)
en1 English Rainman84 2021-05-24 07:19:05 908 Initial revision (saved to drafts)