Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

selfcompiler's blog

By selfcompiler, 5 years ago, In English,

Here is the Link of the topcoder problem Link i read its editorial but not able to get it would anyone like to help me to understand this ??

  • Vote: I like it
  • +6
  • Vote: I do not like it

5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Take it like this:

There must be a 1-coin. Suppose you took k 1-coins, then you can't make k + 1 in any way other than by one k + 1-coin. Now, you have ways to make all values up to 2k + 1. Suppose you took l k + 1-coins. Then you can make all values up to l(k + 1) + k, each exactly once. Again, you need a coin with cost l(k + 1) + k + 1 = (l + 1)(k + 1) to achieve the next value. That looks suspicious: in fact, if you have xi coins of the i-th type, the next coin must have value .

That means if we sorted the coin types that we take at least 1 coin into a sequence of xi, then xi - 1 divides xi and there must be coins of type i - 1; the number of coins of the last type can be chosen easily based on the fact that if it's k, then we can make all values up to kxn - 1.

And now that we know how many coins to use, we can do a DP on the total number of coins used for types starting with the i-th, in O(N2). I leave that up to you.

5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

TopCoder SRM 195 Div 2, Level Three, ChangePurse, Advanced Math. (written for bare purpose of web crawlers to index the page and associate it with related query. wish it was done by tags and headers)