UVa 10313 Pay the price

Блог пользователя aroup

Автор aroup, 9 лет назад, По-английски

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.

dp, uva

aroup
9 лет назад
12

Комментарии (11)

Показать архивные | Написать комментарий?

tenshi_kanade

9 лет назад, # |

First, calcualte the DP. Let DP_i, 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 DP_i, j = DP_i, j + DP_{i, j - 1}. So now DP_i, 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: DP_N, 300
Second type: DP_N, L1
Third type: DP_N, L2 - DP_{N, L1 - 1}

→ Ответить

aroup

9 лет назад, # ^ |

← Rev. 2 →

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 ?

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

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.

→ Ответить

speedster

9 лет назад, # ^ |

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

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

speedster

9 лет назад, # ^ |

sharing code will do.

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

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 DP_c, 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 DP_c, i, j = DP_{c - 1, i, j} + DP_{c, i - c, j - 1}.

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

→ Ответить

determinism

9 лет назад, # ^ |

← Rev. 2 →

Then, your above recurrence relation is incorrect.

Correct one: DP_i, j, k = DP_{i - k, j - 1, k} + DP_{i, 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.

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

← Rev. 3 →

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(N³) memory. I know you can get away with O(N²) 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(N²) version is shorter to code and even simpler to understand. Take a look at my code for a better understanding.

→ Ответить

determinism

9 лет назад, # ^ |

← Rev. 3 →

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

Btw, I know it's not necessary to use O(N³) 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 :/

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

← Rev. 3 →

If DP_i, 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 DP_i, j, k = DP_{i, j, k - 1} + DP_{i - k, j - 1, k}, you just use a 2D array DP_i, j, iterate first by k and do DP_i, j = DP_i, j + DP_{i - k, j - 1}. If you pay attention, it's essentially the same. You're iterating by k first, so DP_i, j is actually DP_{i, j, k - 1} from the 3D version, and you're adding DP_{i - k, j - 1}, which is DP_{i - k, j - 1, k} from the 3D version.