Блог пользователя sojabhai

[SOLVED] Weird TLE | Can anyone explain this
Автор sojabhai, история, 4 месяца назад, По-английски

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 ! :)

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You forgot about memoization in dfs.

→ Ответить
  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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
    → Ответить
    • »
      »
      »
      4 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        4 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Source ?

        → Ответить
        • »
          »
          »
          »
          »
          4 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить