Bekh's blog

By Bekh, history, 3 weeks 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

»
3 weeks 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).

»
3 weeks 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?

  • »
    »
    3 weeks 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.