How to solve this problem about coin changing? Btw, it has a short problem statement.
Thanks.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
How to solve this problem about coin changing? Btw, it has a short problem statement.
Thanks.
Название |
---|
Its the same as naive coin change
No, it needs smarter approach to fit in time constraints.
Simple DP knapsack will work ig.
I don't think so.
It can be solved with inclusion-exclusion principle + dp but idk how.
At first let's solve easier problem with $$$3$$$ coins . Suppose that $$$a_0,a_1,a_2$$$ denotes coins and $$$d_0,d_1,d_2$$$ number of times we can use each coin respectively and $$$v$$$ value we need to get for some query .
Now let's suppose that $$$d_i=inf$$$ for each $$$i$$$ , this is trivial dynamic programming problem (we could do precalculation and then then answer queries) .
If we know answer for above trivial problem we will use inclusion-exclusion dp to answer real problem , suppose that we don't want to count "bad" (one that exceeds $$$d_i$$$) for $$$i=0$$$ . Then we should substract from answer every such possible way that : number of times i used $$$(a_0)$$$ exceeds $$$d_0$$$ . This could be done with taking every number $$$x$$$ , where $$$x>d_0$$$ and substring number of ways to get $$$v-x*a_0$$$ with $$$a_1,a_2$$$ from answer . We will solve similiarly for $$$(a_1),(a_2)$$$ , then for $$$(a_0,a_1)$$$ , $$$(a_1,a_2)$$$ ... and so on .
But we can't iterate over all possible $$$x$$$-es because we would get TLE . Instead of that we will iterate over all possible sums we can get with $$$a_1,a_2$$$ let's denote it as $$$j$$$ . We notice that every $$$x*a_0$$$ is just a form of $$$v-j-(d_0+1)*a_0$$$ and thus we can substract number of ways to get $$$v-j-(d_0+1)*a_0$$$ * number of ways to get $$$j$$$ (with $$$a_1,a_2$$$) instead of iterating over $$$x$$$ . This is solved in $$$O(N*q*max(v))$$$ .
I tried to explain sorry if it's unclear i'm not good with itThanks. I will try to understand this.
Hey, can you explain from where $$$v - j - (d_0 + 1) \cdot a_0$$$ comes from?
This will TLE. I also have a $$$O(N*q*max(v))$$$ solution, tried submitting. But TLE. actually $$$100*100*100000=1e9$$$ operations.
It's also possible to get rid of the factor of $$$q$$$ in the runtime.
At first, precalculate the number of ways to get $$$i$$$ assuming infintely many coins for all $$$0 \leq i \leq max(v)$$$ with a simple $$$dp$$$.
Now consider a "bad" state where we take too many coins of certain types. Let's denote the set of those types by $$$S$$$. There are $$$dp[v - \sum_{i \in S} a_i * (d_i + 1)]$$$ such "bad" states!
Why?
We have to take at least $$$d_i + 1$$$ coins of type $$$i$$$ so that it is a bad state. Doing so, we have already picked coins with value $$$a_i * (d_i + 1)$$$. This has to be done for all coins in $$$S$$$. By subtracting this sum from $$$v$$$ we get the remaining value that has to be achieved somehow. However, the criteria for the "bad" state (taking too many coins of all types in $$$S$$$) is already fulfilled. Thus, it does not matter which coins we take and we can simply use the precalculated $$$dp$$$.
This gives a time complexity of $$$O(N*(max(v) + q)) = O(N*max(v))$$$
I have a hard time understanding why just taking everything $$$d_i + 1$$$ times is enough. What about when we take $$$d_i + 2$$$, $$$d_i + 3 ...$$$ times and so on? Aren't those also a bad states? Can u explain?
Thanks.
Oh, I think I got it. Taking $$$d_i + 2$$$ in dp solution comes from taking $$$d_i + 1$$$, maybe?
The key is that everything is taken at least $$$d_i + 1$$$ times. This is done by taking $$$d_i + 1$$$ elements in the first step and then filling up with arbitrary coins. So we might still end up taking $$$d_i + 1, d_i + 2, d_i + 3, ...$$$