mezhaka's blog

First encounter of the "implementation matters" given the complexity is equivalent.
By mezhaka, 13 years ago, In English

I have failed to submit div. 2 B problem in round #92 with the "Time limit exceeded" verdict. Later I have modified my solution and now it does pass the test, but the interesting part of it is that the complexity of both is equivalent (please correct me if I am wrong). This is the first time I encounter such a problem. Usually if you got the solution with the right complexity it does pass the test. For those who are interested in looking at the code it is here: http://pastebin.com/scSwyuEq. The fast function is f, the slow one is f1 (if you want to run the slow one, then just swap the names).

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

13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Complexity doesn't matter too much when inputs are small, ex. insertion sort performs better than merge sort on small inputs, brute multiplication O(n^2) and FFT, and can become even worst, the constant factor can't be always ignored... it depends on processor architecture, caches... should not happen, but:
"In theory there is no difference between the theory and practice, in practice there is..."
→ Reply