Given a List of coins, find minimum number of coins that need to be added to list so that all prices from [1,P] can be paid using the coins of list.
Constraints Length of coin list<=100000 Value of coins <=1000 P<=10000
Sample: P=19 Coinlist={1,4,10} solution=2
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
This may be solved with DP, but it does not need to be. There is a greedy solution based on the necessary condition on whether a prefix of the increasingly sorted coin list with sum $$$S$$$ can make up all subset sums in $$$[1,S]$$$.
any links for the question you mentioned, would be helpful
I remember solving a task almost equal to the task I explained, but I forgot the link to it. I'll update the comment if I find it out. Anyways the main theorem and the proof is as follows if you were wondering.
WLOG assume that $$$a$$$ is sorted (sort it if it isn't). Assume for some prefix $$$a_1,a_2,\cdots,a_k$$$ the sum is $$$S_k$$$, and it generates all integers in $$$[0,S_k]$$$. Then $$$a_{k+1}$$$ must be equal to or less than $$$S_k+1$$$ for the new prefix $$$a_1,a_2,\cdots,a_{k+1}$$$ to generate all subset sum in $$$[0,S_k+a_{k+1}]$$$. We can prove this by contradiction. If $$$a_{k+1} \ge S_k+2$$$, then we cannot generate the integer $$$S_k+1$$$, and thus $$$a_{k+1}$$$ is at most $$$S_k+1$$$. If $$$a_{k+1} \le S_k+1$$$, then we can trivially generate the integers in the range $$$[a_{k+1},S_k+a_{k+1}]$$$. As the two ranges are continuous, we conclude that we can generate every integer in $$$[0,S_k+a_{k+1}]$$$. Thus, $$$a_{k+1} \le S_k+1$$$ is both necessary and sufficient to generate all subset sums in $$$[0,S_k+a_{k+1}]$$$.
UPD: the task was "No change" from EIO 2020-21
can you please provide code
if you have coinst with value 1 and 2 why can't you make all the coins
Number of times a value is present in coin list, that value can be used only that many times
let the array be arr (0 indexed) , and the corresponding prefix sum array be pre (in the pseudo code , prefix sum array is considered as 0 indexed) here is the pseudo code