ThunderStroke's blog

UVa — 10313 — Pay the Price — TLE
By ThunderStroke, history, 9 years ago, In English

Got TLE...:(

What should I do now??

Any optimization idea??

Problem Link

Solution Link

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hmm.. Thanks.

    But I m not clear with recursion's complexity.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply