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

Weird TLE | Can anyone explain this
Автор sojabhai, история, 6 часов назад, По-английски

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

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

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

You forgot about memoization in dfs.

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

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

        Source ?

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

          → Ответить