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

getting time limit exceeded on SPOJ "MCOINS — Coins Game" problem.pls someone help me.
Автор mahim007, история, 9 лет назад, По-английски

problem link->MCOINS — Coins Game

my code-> codepad

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well let's consider the example. We have :

      2 3 5 
3 12 113 25714 88888

      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?

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        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.

        → Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить