Блог пользователя ahilaan

Автор ahilaan, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.