In the recent div3 contest, many C++ solutions that used unordered maps were hacked which is reasonable due to hash collisions. However, python dictionaries are ordered maps as far as I know, still my solution got hacked. I can't think of any other issue which might have caused a TLE. Here's my submission: https://codeforces.me/contest/1980/submission/263979357









I dunno but I'm sure dumping Python is the optimal solution either way.
Python dictionaries are unordered maps. They do not store in sorted order.
I think theyre ordered in PyPy 3.10 and above
actually no, they are ordered in terms of insertion time (so that when you iterate, you see the elements in order of when you inserted them into the map), they are not ordered in the same way as C++ (in terms of numerical value of key)
Python dictionary are not ORDERED(it is unordered), then it is hackable using same way with hacking C++ unordered_map(I got hacked because it too (┬┬﹏┬┬) )
So we were expected to use some external class?
my solution to use python dictionaries without getting hacked is to store numbers in form of string. I had read somewhere that doing this avoids most easy ways of getting hacked. I am not sure if this is as unhackable as c++ ordered set though.
So there is no tree based set implementation in python?
sortedcontainers provides tree based set and dict.
but you can't use it in the codeforces submissions, can you? I thought only built-in, default libraries in the language can be used.
Genius lol
Calling Python's
dict"ordered" can be a misnomer -- it's a hash table that just preserves the insertion order. It basically corresponds to C++'sstd::unordered_map. Actually, adictcan hold elements that are not comparable.