snorkel's blog

Coin changing variation
By snorkel, history, 3 years ago, In English

How to solve this problem about coin changing? Btw, it has a short problem statement.

Thanks.

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

Comments Comments (12)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Its the same as naive coin change

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No, it needs smarter approach to fit in time constraints.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple DP knapsack will work ig.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think so.

    Hint
    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 it
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I will try to understand this.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, can you explain from where $$$v - j - (d_0 + 1) \cdot a_0$$$ comes from?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    This will TLE. I also have a $$$O(N*q*max(v))$$$ solution, tried submitting. But TLE. actually $$$100*100*100000=1e9$$$ operations.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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))$$$

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I think I got it. Taking $$$d_i + 2$$$ in dp solution comes from taking $$$d_i + 1$$$, maybe?

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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, ...$$$

        → Reply