IcantComeUpWithOrigName's blog

Does efficiency of code really matter in cp?
By IcantComeUpWithOrigName, history, 5 years ago, translation, In English

How often are situations, when you have solved problem earlier or at the same as other participants, but he is above you because his code is faster and consumes less memory?(Given that both codes are fast enough to pass all test cases) Is it possible on codeforce or any other platform and tournament? In that case how often does it happen? Sorry, for grammar, I am not a native speaker.

  • Vote: I like it
  • -4
  • Vote: I do not like it

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

Auto comment: topic has been translated by IcantComeUpWithOrigName (original revision, translated revision, compare)

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

As long as both solutions pass all the test cases, efficiency does not matter in competitive programming. The one who submitted earlier doing fewer mistakes will get the better rank.

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

In general, you want your code to be as easy to code as possible so that it is only as efficient as it needs to be. Don't bother trying to make something linear if it would require a bunch of thinking and you can just mindlessly binary search for the answer anyway.

That said, when it gets to harder problems, occasionally you will either need to optimize your solution to lower the constant factor (which is always annoying), or do some nonsense to get rid of log factors, such as using an RMQ to answer queries in O(1) instead of a segment tree in O(log(n)).

In practice, the latter usually happens when your logic is already built on top of some other log factor, for instance you are doing something for each power of 2, or you are binary searching something, et cetera.

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

    That was the smoothest segue into self-promotion I've ever seen xD. +1

    (On a more serious note that video is very educational and helped me understand RMQ) :D

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

Execution time and memory don't matter on Codeforces as long as they're below the limits. It's the same for all other contests that I know of.

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

In (Uva) currently named onlinejudge.org, there is a rank list based on the efficiency for each problem.

→ Reply