sojabhai's blog

Weird TLE | Can anyone explain this
By sojabhai, history, 6 hours 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
  • +2
  • Vote: I do not like it

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

You forgot about memoization in dfs.

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

        Source ?

        → Reply
        • »
          »
          »
          »
          »
          5 hours 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