Problem link: https://codeforces.me/problemset/problem/2060/C
1st Submission: https://codeforces.me/problemset/submission/2060/305937191
2nd Submission: https://codeforces.me/problemset/submission/2060/305932678 Language used: Python
Not an input/output related issue.
After my submission, I checked some accepted solutions. Some of them even sort the numbers before solving. It is supposed to take nlog(n).
In any case I tried to sort the map keys, so that I don't have to iterate through all map/dictionary items. But even then I'm getting TLE. Is it the choice of data structure?
Can someone help me understand what is going wrong. I am trying to learn for future problems.
Also, would be great if someone can share any resource for python optimizations to avoid TLE
New user posting for the 1st time. Please let me know if I missed any information.
Auto comment: topic has been updated by yodacodes (previous revision, new revision, compare).
I'm not python master, so I don't really know if your solution is acceptable, but:
try not to rely on hashmap/dictionaries 305951696
try fast input/output sys.stdin.read, sys.stdin.write
Edit: wrong submission number
You can use the two pointer way since if Alice chooses a number and that is possible to be k minus a = b then Bob will choose b, otherwise, he will choose anything else that a plus b not equal to k: My submission: my code
i would generally suggest you to try C++ for once cuz python processes every single line which makes it slower in the cases, of recursions and loops, or the alternative way is the learn to use threadings i genreally use python for ML and stuff
Python maps have a similar flaw to C++ unordered maps, where they can become worst case O(n) per operation (see https://codeforces.me/blog/entry/62393 ). I'm not sure if there is a great way to get around this, but I have 2 ideas
Find a python implementation of a red-black tree (which is what c++ uses for its map) and use it instead of map / set
Use C++, I know it might be hard, but trust me it is worth it.