Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

sojabhai's blog

[SOLVED] Weird TLE | Can anyone explain this
By sojabhai, history, 2 years ago, In English

The D problem in the Div 2 round Yesterday

270778100 — AC

270777306 — TLE

Reference Variable for accessing DP leads to tle

Any explanation ?

Thanks a lot ! :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

You forgot about memoization in dfs.

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

    The whole point of using reference variable is memoisation itself 

    int &an = dp[x][lastSeen]; 
// whatever changes I make to this variable will be reflected in the dp array as well
    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Sorry, idk what is this. Im not c++ guru :( My thought is that linking and unlinking variable is time consuming and not O(1).Because you first allocate space in the heap and create a connection, then cut it off, which gives additional costs both in memory and time. So its causing tle.

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

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

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

I think it's the fact that $$$dp[x][lastSeen]$$$ is accessed multiple times in the TLE code (even if it's via a reference variable), and it's probably not cache optimised. Replacing the reference variable with just $$$dp[x][lastSeen]$$$ gives the same TLE result — 271896757

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

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

→ Reply