Weird Time Limit Exceeded in DP with change in only one line of code (Way of checking if a state is visited)

Revision en4, by Bekh, 2019-06-25 01:51:58

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Bekh 2019-06-25 01:51:58 67 Tiny change: 'roblem/C) \nAC Code ' -> 'roblem/C) \n\nAC Code '
en3 English Bekh 2019-06-25 01:49:41 14
en2 English Bekh 2019-06-25 01:47:14 64
en1 English Bekh 2019-06-25 01:45:35 755 Initial revision (published)