myaw's blog

Strange Runtime error
By myaw, history, 9 years ago, In English

Hi everyone.

I was trying to solve small input for this problem using recursive dp.

But it gives a strange runtime error when n >= 180000.

this my code

Any helps.

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

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

I think u have issues with stack size.

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

    "u have" Is that mean that is my machine problem ? does it work for you ?

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

      Yep, everything works fine on my PC, you should either allocate bigger stack or avoid recursion. (I believe it is not that hard in that task, simply use std::stack or array instead of recursion)

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

You can also iterate backwards through the dp states before answering. If your dp recurrence goes "forward" ( dp(x) depends on dp values greater than x) fill the values from MAXN to 0. Doing that the program will never reach a recursion depth greater than 1. It is a cheap and fast way to fix this kind of issue.

→ Reply