ghorardim's blog

UVA-562 — Dividing coins problem getting TLE
By ghorardim, history, 9 years ago, In English

I am getting TLE and I can't handle it.I know the is solved by 0-1 Knapsack.I also try this. I think i have some mistake in my code but I do not found it. Please anyone help me..... Problem :UVA-562 — Dividing coins my code :Cpp_Code

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

Comments Comments (3)
| Write comment?
»
9 years ago, hide # |
← Rev. 4  
Vote: I like it 0 Vote: I do not like it

Consider the following test:

100

1 cent 99 times and 500 cents

Your solution will run up to O(2^n) in this case.

Add memo: for each state (i, sum) memoize the answer obtained so that you can get it in O(1) afterwards.

→ Reply
  • »
    »
    9 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    how can i do that???i don't found any idea.

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it 0 Vote: I do not like it

      int knap(...)

      if dp[i][sum] is already calculated

      return dp[i][sum];

      if (i == n)

      ...

      ...

      ...

      return dp[i][sum] = max(q1, q2)

      Note that there are some states that will never be reached. So my advice is to do the following thing:

      int knap(...)

      if visited[i][sum] return dp[i][sum]

      if (i == n)...

      visited[i][sum] = true

      ...

      return dp[i][sum] = max(q1, q2)

      → Reply