HidenoriS's blog

By HidenoriS, 8 years ago, In English

I was working on problem D on Round 166 Div 2.

This is my submission which got TLE.

The interesting thing is that I copied the solution above and submitted exactly the same code again, and I got AC.

I submitted the TLE code multiple times, and all of them got AC.

More interestingly, my code outputted the correct solution, but I got TLE. (You can see it by comparing the output for test 8 on those two codes)

Could someone help me figure out how this happened?

Thank you.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This two submissions were made with different selected compiler MS C++ and GNU C++. May this influenced such result.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't realize that so I tried it just now. I still got AC twice in a row. first and second.

    MS C++ seems slightly slower though.

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There is a notice at the task page:
"""
Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, than value 800 ms will be displayed and used to determine the verdict.
"""
Maybe your solution works near 1000ms (time may slightly vary depending on the general load of the machines), and then this time got multiplied by two, hence the time difference (850-1000ms difference looks smaller than 1700-2000ms).

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That makes sense. It's probably safer to optimize code as much as possible before submission in contests with that notice.

»
7 weeks ago, # |
  Vote: I like it -39 Vote: I do not like it

Hey!!

This is in reference to my submission https://codeforces.com/contest/1698/submission/162126884 .

The code I submitted during contest says that its correct but now giving TLE on 13th T.C..

I have again submitted the same code with GNU C++20 (64) lang and now its AC again.

Please check it and give me the ratings for my submission during the contest. It could have thrown the error during contest itself so I might have tried with rest of the approaches but it didn't do so..

So there is none of my mistake. I think the judge should have a look at my submission and give me the required ratings! Thnaks

  • »
    »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    First of all, it is preferable to comment somewhere other than an 8-year-old thread. I notice you used an unordered_set in your solution. The default hash function is prone to blowing up to certain numbers. It is likely that your solution failed system tests due to this. Your in-contest submission used C++17, which may have a different default hash function than C++20, which is why the C++20 submission did not TLE. Although it's unfortunate that this happened, the problem was setup this way. A lot of people FSTed due to this.

    Read more about unordered_set/map here: https://codeforces.com/blog/entry/62393