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

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

Got TLE...:(

What should I do now??

Any optimization idea??

Problem Link

Solution Link

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

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

300^4 complexity will definitely not get you accepted. Lose the loop inside the dp state, convert the loop into two state calls as taking the current coin and not taking it. Also, why are you clearing dp array for each case? You only need to do it once. For 'tot' parameter in dp state, you went backwards. Do the same for 'term' parameter.

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

    Hmm.. Thanks.

    But I m not clear with recursion's complexity.

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

      Ok, crux of it goes like this: the number of parameters you have for a single dp state, multiply their worst cast limit together. Plus if you have inside loops inside the dp state, those factor in too. You have 3 parameters here, namely 'ind', 'tot' and 'term' whose maximum values can be 300. So we get 300^3 by multiplying them. You also have a loop going on inside the dp state which adds an iteration of 300 at most. That's how you get 300^4 or O(N^4) complexity.