CQXYM's blog

Crazy Code?
By CQXYM, history, 3 years ago, In English

Yesterday, I took part in Codeforces Deltix Round Spring 2021 [Div.1 + Div.2], and happened something incredible.

I solved out the problem D and pasted the pretest(37), but I failed the system test(36).

My original code

Later accepted one

The two codes are almost the same. Though my algorithm is to solve the problem randomly, it shouldn't exit a the time of 1.6s. Is there something wrong with my original code, or is there anything else wrong with the platform?

Thanks.

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

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Maybe because you are using random shuffle which could be different in both submissions

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

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

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

From some research I did, clock() is platform dependent and in Linux, you will get CPU time, while on Windows you will get wall time.

CPU time, in short, is the time spent by the CPU on your program. On the other hand, wall time is the time spent in total(which can involve time spent by the CPU to start executing your program/waiting for executing your program).

Sources

https://levelup.gitconnected.com/8-ways-to-measure-execution-time-in-c-c-48634458d0f9

https://stackoverflow.com/questions/7335920/what-specifically-are-wall-clock-time-user-cpu-time-and-system-cpu-time-in-uni

Edit- Looks like codeforces runs under window OS, which mean the time you are getting using clock() is walltime which isn't necessarily the execution time, and could have extra things like the time your program waits for it's turn to be executed on the CPU.

Source for my claim above https://codeforces.com/blog/entry/4088

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

    Thanks. I got it, but how can I avoid these kind of problems?

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

You're using random_shufflewhich is not determinant and depended on std::rand which returns random number in [0; RAND_MAX] which is small (not guaranteed but I don't know any otger value than 32767.

So you most likely shuffle only small part of vector.

Use shuffle instead

→ Reply