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

Why 0 index hashing is faster than 1 index hashing?
Автор redheadphone, история, 2 года назад, По-английски

This has happened to me twice, where 1 index hashing is getting TLE but 0 index hashing with same logic is getting Accepted. Not sure if it's python issue or hashing complexity.

TLE — https://codeforces.net/contest/1701/submission/163370464

Accepted — https://codeforces.net/contest/1701/submission/163370574

TLE — https://codeforces.net/contest/1702/submission/163995656

Accepted — https://codeforces.net/contest/1702/submission/163996134

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

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

If you look at the test cases, both submissions TLE'd on the same sequence. In fact, this sequence appears in several other contests such as 803C. So I believe that this was an anti-hash test specifically designed to counter a Python hash table that does not change the default 1-based indexing.

→ Ответить
»
22 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Okay, so turns out that this was due to Anti hash table test and 0 index hashing is not faster than 1 index hashing, the testcase can be designed based on index so that your solution exceeed time limit.

you can find more about it on https://codeforces.net/blog/entry/101817 (thanks to robostac who shared that blog)

One of the fix mentioned in that blog which can prevent others from hacking your solution was wrapping hashmap key

you can use what I use in my template https://github.com/RedHeadphone/CP-template-python

RANDOM = random.randrange(2**62)
def Wrapper(x):
  return x ^ RANDOM
→ Ответить