aayush_chhabra's blog

Same code gives TLE in contest but AC after contest
By aayush_chhabra, history, 20 months ago, In English

Hey MikeMirzayanov In the recent div2 contest, I encountered an issue where my code for Problem D, "A Wide, Wide Graph," resulted in a TLE. However, I submitted the same code today and it was accepted.

Tle Submission:Tle

Ac Submission:AC

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
20 months ago, # |
  Vote: I like it +23 Vote: I do not like it

998ms means about to TLE

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 2   Vote: I like it -27 Vote: I do not like it

    Ya ik it is very close to time limit but because of unconsistency may be due to load on site sometimes it is just below and sometimes it is just above the time limit

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this, i think, means that this isn't the intended complexity, it just happened to be >=2ms faster the second time. This is precisely the reason why many coders would submit multiple solutions to a problem trying to get their runtime down, to make sure it wasn't a fluke.

Still, interesting situation though.

Also 18o3 orz.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    🤡 🤡 🤡

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

    As far as the logic is concerned and intended complexity it is fully fine it is just the time python takes

    → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Use PyPy3 instead, it would much faster.

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

    With dfs it gives runtime more so python 3 is best choice for dfs related stuff

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

      For dfs, I recommend you convert dfs to stack version. I was in the same situation in the past.

      At that time, I try to 2 experiments:

      1. Use python3 and set a recursion limit, it's work but need carefully when choose a recursion limit.

      2. Continue use Pypy3 (it isn't work with set a recursion limit -> memory error). I convert dfs to stack version

      Although both ways can AC but Pypy3 still faster and stable than Python 3 version (both recursion and stack implementation) in run time.

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

        converting to stack version makes the problem tough for sure . like it makes +100 tougher

        → Reply