aroup's blog

UVa 10313 Pay the price
By aroup, 9 years ago, In English

I got stuck with this problem for quite a time now.It can be counted how many ways to make N with a number of coins.But I have no idea how to answer range query for this problem.

Problem Link

Any detailed hint of overall solution of this problem,it will be so much helpful.Thanks in advance.

Tags dp, uva
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

First, calcualte the DP. Let DPi, j be the way to pay i dollars using exactly j coins. Calculate the DP the normal way (judging from your post, I assume you already know how to do that), and then sum the previous values. That is, for all [i, j], set DPi, j = DPi, j + DPi, j - 1. So now DPi, j means the way to pay i dollars using at most j coins.

Another thing to notice is that there's no way to pay a price  ≤ 300 with more than 300 coins. Now, to answer the queries...

  • First type: DPN, 300
  • Second type: DPN, L1
  • Third type: DPN, L2 - DPN, L1 - 1
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Would you please elaborate why for the third type : DP [n,l2] — DP[n,l1-1] would work ?

    Normally I would try to do it with a for loop,but constraints are large.Why this thing would work like range sum ?

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

      Just think about it, if you do (1 + 2 + 3 + 4 + 5 + 6 + 7) - (1 + 2 + 3 + 4), you get (5 + 6 + 7). This is the same idea.

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

    tenshi_kanade I thought the same . but there is something more to this question . quote from the question " For example, by using three coins one can pay six dollars in 3 ways, 1+1+4, 1+2+3, and 2+2+2" but if we do by conventional method this would have 1+1+4 and 4+1+1 as 2 different ways of paying as simply answer would have been n+k-1 C k-1 ( x1+x2+x3...xk=n and x1,x2,x3..xk>=1) which results into different answer

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

      To overcome that issue, you can iterate by coin value, then by price, then by amount of coins. If you do it that way, you can make sure that first you count all ways that use up to coin with value v, then all ways that use coins with value up to v + 1, etc..

      I can share the source code if I'm not clear enough...

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

        sharing code will do.

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

          OK, here it is: C++ Code

          As you can see, to make sure we don't count one way many times, we first iterate by coin value c, then by price i, then by amount of coins j.

          Perhaps if I had used a 3D array DPc, i, j that stores the ways to pay i dollars by using exactly j coins with values  ≤ c, , it might be clearer and easier to understand. In tbat case, the transition would be DPc, i, j = DPc - 1, i, j + DPc, i - c, j - 1.

          But it's not necessary to use O(N3) memory, so I just coded the shortest and more efficient form using O(N2) memory.

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

        Then, your above recurrence relation is incorrect.

        Correct one: DPi, j, k = DPi - k, j - 1, k + DPi, j, k - 1

        that is the number of ways of getting i dollars using j of first k type coins. DP array is 2-dimensional because of memory optimization.

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

          What is incorrect? I don't know what you mean.

          The way you describe here is what I explained above, but it's not necessary to use O(N3) memory. I know you can get away with O(N2) memory even with this method by having a [2, 300, 300] array and working modulo 2, but even that is unnecessarry. By the way the transitions are calcualted, you only need a 300x300 2D array to do the DP.

          Besides, I think that the pure O(N2) version is shorter to code and even simpler to understand. Take a look at my code for a better understanding.

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

            I think I misunderstood you. Can you explain your pure O(N2) ?

            Btw, I know it's not necessary to use O(N3) memory. What I was trying to say was that having 2-dimensional array doesn't mean that recurrence relation has 2 variables.

            UPD: I just saw your new comment. While I was writing my answer I didn't see your last comment. I was mentioning what you wrote in you first comment, that's why I said recurrence relation is wrong. Sorry for confusion :/

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

              If DPi, j, k is the number of ways to pay i dollars using j coins from the first k types of coins, then instead of doing DPi, j, k = DPi, j, k - 1 + DPi - k, j - 1, k, you just use a 2D array DPi, j, iterate first by k and do DPi, j = DPi, j + DPi - k, j - 1. If you pay attention, it's essentially the same. You're iterating by k first, so DPi, j is actually DPi, j, k - 1 from the 3D version, and you're adding DPi - k, j - 1, which is DPi - k, j - 1, k from the 3D version.

              When I mean pure O(N2), I'm talking about pure quadratic for memory. Clearly, the runtime will always be O(N3).

              → Reply