redheadphone's blog

Why 0 index hashing is faster than 1 index hashing?
By redheadphone, history, 2 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

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

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.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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
→ Reply