Bekh's blog

Weird Time Limit Exceeded in DP with change in only one line of code (Way of checking if a state is visited)
By Bekh, history, 5 years ago, In English

Hi,

The Problem

AC Code (2.5s): 56017075 (Or here if you can't view gym submissions)
TLE (over 30s, tested on custom private group contest with custom TL): 56017081 (Or here)

Regardless of the problem and its solution, the ONLY line that changes between the 2 submissions is the way I check if the state was calculated before or not. When I check it using if (ret != -1) it gives TLE, but when I check it using visit array is (visit[i][j] == vid) it passes. I don't even remove the extra memset for memoization array in each testcase when using the visit array. Why would this very small change result in that huge difference in time?

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bekh (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

clearly if u check if (ret != -1), solve(i,j) will be computed many times if solve(i,j) is indeed -1 even if you have visited it before? So there's no time complexity guarantee in the state, and therefore if most of solve(i,j) is -1, you solution is as slow as bruteforce?

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

    Zzz. Thank you. I just noticed that. Completely forgot that the input got negative values even tho it was included in sample.

    → Reply