ahilaan's blog

By ahilaan, history, 2 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I dunno but I'm sure dumping Python is the optimal solution either way.

»
2 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Python dictionaries are unordered maps. They do not store in sorted order.

  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I think theyre ordered in PyPy 3.10 and above

    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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)

»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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 (┬┬﹏┬┬) )

»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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++'s std::unordered_map. Actually, a dict can hold elements that are not comparable.