problem link->MCOINS — Coins Game

my code-> codepad

# | User | Rating |
---|---|---|

1 | tourist | 3534 |

2 | LHiC | 3279 |

3 | moejy0viiiiiv | 3196 |

4 | ainta | 3174 |

5 | Petr | 3135 |

6 | Um_nik | 3098 |

7 | -XraY- | 3086 |

8 | W4yneb0t | 3068 |

9 | Merkurev | 3055 |

10 | I_love_Tanya_Romanova | 3037 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 177 |

2 | rng_58 | 171 |

3 | Petr | 160 |

4 | csacademy | 155 |

5 | Swistakk | 152 |

6 | Zlobober | 149 |

7 | GlebsHP | 148 |

8 | zscoder | 137 |

8 | Um_nik | 137 |

10 | Xellos | 134 |

10 | Radewoosh | 134 |

10 | lewin | 134 |

problem link->MCOINS — Coins Game

my code-> codepad

↑

↓

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/27/2017 04:12:16 (c3).

Desktop version, switch to mobile version.
User lists

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.

Although I got AC in one go the time was 0.34seconds.But after optimizing my algorithm according to your suggestion time reduced to 0.01seconds.Thank You ;)

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