K_B_G's blog

issue regarding problem D edu round 106
By K_B_G, history, 4 years ago, In English

During Yesterday's EDU round, My solution to D was accepted and during system testing, it got TLE on test case 60. AC during contest : (https://mirror.codeforces.com/contest/1499/submission/110354551)

Now I submitted the same code multiple times after system testing is over, it is getting accepted. AC after system testing : https://mirror.codeforces.com/contest/1499/submission/110419651

So can anyone please tell what can be wrong in this scenario ?

  • Vote: I like it
  • +67
  • Vote: I do not like it

Comments Comments (28)
| Write comment?
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

same with my submissions....

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +26 Vote: I do not like it

Yes, I am having similar issues. All submissions are almost the same, you can compare. I think that the time limit to this problem is not optimal.

Submission 1 : https://mirror.codeforces.com/contest/1499/submission/110420452

Submission 2 : https://mirror.codeforces.com/contest/1499/submission/110390562

PS: the same code Submission : https://mirror.codeforces.com/contest/1499/submission/110420816 gives tle on test 39 now.

PS (yet again) : The SAME CODE is $$$Accepted$$$ now!!! Solution : https://mirror.codeforces.com/contest/1499/submission/110421153

Just change the way you write $$$2\times 10^7$$$, you will get tle. Solution : https://mirror.codeforces.com/contest/1499/submission/110422095

I have made some minor changes in each submission, so that Codeforces allows me to resubmit.

Admins please look into this issue, to either increase the time limit of this problem or take some other steps you might find suitable in this case.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    To all the people that passed with 1996ms, you just got extremely lucky, nothing more than that. Your solutions should have failed. Extra log factor adds 500ms to the execution time in this case, and that ruins the purpose of this problem, it's a D2D, all the details matter. If you really want to make it fair — than take the time limit down to 1.9s, and the lucky ones will get removed. There are dozen of non-optimal implementations which will pass if you increase TL from 2 to 2.2-2.3 seconds. Come on, it's just one contest, don't blame tests for your mistakes.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -15 Vote: I do not like it

      .

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I'm sorry, but I don't understand random gibberish. Rephrase your sentence/translate it to English so we all understand you. :)

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

      Blaming tests? It's the time limit I said for. And yes, even if the time limit is decreased it is completely okay, at least those lucky ones get filtered out.

      → Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I don't know the specifics of why it happened, but I think it's something to do with a bit of random variance when running a program.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Yep, that happens, its just that every time you run a program it won't run in exactly the same time, there will always be minor fluctuations in runtime, for example this submission ran in around 1980 ms during the contest but I figured it would probably TLE out in system test so I optimised it a bit and submitted it again here which ran in around 1700ms during the contest, It barely passed on system test with 1996ms :/

So yeah, optimise as much as you can.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    there are many people who got accepted and have 1950ms or above time limit during contest.

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

      Yes, as I said runtime fluctuates by a bit, so for a program that should take 1000ms, sometimes it may take 1050ms and sometimes it may also run in 950ms, as a result some people's solution might TLE out while some of those solution may also pass due to those minor fluctuation even though they had roughly the same runtime during the contest, as such we can't really do much about this and therefore our best option is to just optimize as best as we can.

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

        yes i am completely agree with you but this is biased.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Randomness is not being biased. Optimize your solution so you don't have to rely on randomness to get an AC.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Dude what do you mean? this is completely random.

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

    Yeah my solution also ran in 1996 ms

    But Why do we have such random run time despite having a same time complexity and same constant factor(i guess)?

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

      The truth is you don't. If you remove vis array from solution. You get 1600ms runtime, it's your fault, it's not needed. Were you able to estimate 2e7 log 2e7 takes about 0.5s to execute => your solution is nowhere near optimal, because you do useless calculations. Come on, it's a D2D, what do you expect, writing a 0.5s random for loop and expecting to pass? 110425446

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

same issue with me
tle:110372505
now passed: 110421066

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Same issue TLE: 110405479 AC: 110422060

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think sometimes if the time limit is so strict they should rejudge the solutions by increasing the time limit by small amount

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

No need to rejudge, there was more than enough time for solutions to pass. It's your fault choosing to use unoptimal strategies. Simplest sieve passes all the tests in about ~1.3s. Take a look at icecuber's submission and you'll see what I'm talking about. It's the same as saying, please increase the time limit I used map instead of unordered_map.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Same issue https://mirror.codeforces.com/contest/1499/submission/110380734 and https://mirror.codeforces.com/contest/1499/submission/110424412. I hope admins look into this.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Your factorization is not optimal — therefore you waste ~500ms. It can be all done in one for loop, no need for another log factor. You add n log n execution time in the worst case, which is ~2e8 operations, these solutions should be intended to fail, when you add such a large factor for no reason.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to get the runtime close to 1000 ms with some precomputation with sieves. Can anyone help optimize this any further? I would be very grateful

https://mirror.codeforces.com/contest/1499/submission/110425912

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Same thing happened with me.see this 110380490 and this 110426784.MikeMirzayanov sir these submissions are same.still one passing after sys test and another giving tle during sys test

→ Reply