Have the CodeChef servers become faster?

I made a few observations for a few of the problems in the March Long Challenge and was curious to know your thoughts.

  • COLGLF4: I wrote an O(N) solution that passed in 0.06 seconds. The total number of operations in this case would be T\cdot N which is about 2\cdot10^{11} operations in a second.

  • PAPARAZI: For this problem my solution was a naive convex hull implementation that runs in O(N^2) worst case. This runs in 0.08 seconds and I’d say is T\cdot N^2 operations worst case. This is in total 2.5\cdot10^{15} operations in a second.

I’m used to having maybe a billion operations running running every second. Is this a recent change by CodeChef?

  1. In COLGLF4, it is mentioned sum of N over all test cases does not exceed 10^6, so O(N) was only expected.
  2. In PAPARAZI, I see you have done some optimization, but if you think your solution is O(N^2) then test cases might be weak.
3 Likes

You might want to check out this comment, PAPARAZI - Editorial - #13 by suman_18733097
You have an O(N) implementation without realizing it.

Don’t expect Codechef servers to change your code running time…

1 Like