problem link->MCOINS — Coins Game
my code-> codepad
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
problem link->MCOINS — Coins Game
my code-> codepad
Name |
---|
Your solution has complexity of O(N) per single tower, which results in O(m*N) per test-case which unfortunately is not fast enough. One could easily notice, however, that the dp states will be the same for the same K and L and are independent of N, so you can compute the states only for the largest tower (biggest N), thus resulting in O(N) per test-case.
I managed to get AC modifying your code to do just that, so feel free to ask any questions :)
sorry for my late reply. would u kindly describe the way more elaborately?? since i am new to dp i find it difficult :( any clue,hints,idea will be greatly appreciated :)
Well let's consider the example. We have :
So what your solution will do is calculate the states from 1 to 3, then from 1 to 12, then from 1 to 113, then from 1 to 25714, then from 1 to 88888. However you can instead calculate them just once from 1 to 88888 and then use dp[3], dp[12], dp[113], dp[25714] and dp[88888] to answer your queries. Do you understand what I mean?
yes Enchom bro,i completely understand your idea.even if i never understand a problem so well before :D i implement as you said and got accepted :) :) thank u so much.
hey.. can you please give me any hints on writing a recursive solution to this problem.. I would be so grateful if you do :D
Click
thanks for the explanation... got AC using recursion :)