sojabhai's blog

[SOLVED] Weird TLE | Can anyone explain this
By sojabhai, history, 5 weeks 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

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

You forgot about memoization in dfs.

→ Reply
  • »
    »
    5 weeks ago, # ^ |
      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
    • »
      »
      »
      5 weeks ago, # ^ |
        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
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Source ?

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

          I only have link to Russian c# video. I think you dont need it. Its just base knowledge about struct, collections,heap,stack and how reference and pointers work.

          → Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  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