I was doing G1 (https://mirror.codeforces.com/contest/1822/problem/G1) and came up with this solution which is O(n * sqrt(m)) as stated in the editorial. This TLEs in testcase 13 due to constant factors.
TLE Code 1
I went to further optimise my code as shown here, which TLEs in testcase 16:
TLE Code 2
Main changes:
- Use faster output
- Use Counter instead of array to count, which is faster (this helped the most, and got me past testcase 13). Initialising the count array at the very start instead of for each testcase also helped me to pass everything.
- Got rid of unnecessary variables, if else checks and array / counter access.
- Use for loop instead of while loop
However, this still TLEs due to Testcase 16, which is a hash hack for Counter. If I sort the input beforehand, my code passes!
Code that works
Note that Python is too slow to pass all testcases (it fails at testcase 13), but PyPy works.
I have a few questions for the people well versed in python:
- Why does sorting the input help get rid of the Counter hash hack testcase TLE?
- Is it possible to make Python pass all testcases? (Edit: I found a submission that works in python https://mirror.codeforces.com/contest/1822/submission/203361435)
I hope you can answer my questions, if not, I hope you have learnt something from my blog. Thank you!