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 ??

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 169 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 153 |

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 ??

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 21:45:24 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Take it like this:

There must be a 1-coin. Suppose you took

k1-coins, then you can't makek+ 1 in any way other than by onek+ 1-coin. Now, you have ways to make all values up to 2k+ 1. Suppose you tooklk+ 1-coins. Then you can make all values up tol(k+ 1) +k, each exactly once. Again, you need a coin with costl(k+ 1) +k+ 1 = (l+ 1)(k+ 1) to achieve the next value. That looks suspicious: in fact, if you havex_{i}coins of thei-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

x_{i}, thenx_{i - 1}dividesx_{i}and there must be coins of typei- 1; the number of coins of the last type can be chosen easily based on the fact that if it'sk, then we can make all values up tokx_{n}- 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, inO(N^{2}). I leave that up to you.thanx xellos

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)