mohamedhesham's blog

Why HashMap sometimes getting TLE ?
By mohamedhesham, history, 6 months ago, In English

in the last codeforces contest Codeforces Round 950 (Div 3) , i made up to 500 hacks for both solutions of c++ and python. but why?

First let me explain why for Python : the main collections that hack the sol. in python is Counter (collections) , but why?

It is not an issue related to python slowness, but it is related to hash collisions being o(n^2) but imagine with me if you : sort the array before you use counter, it should pass or try random.shuffle on points instead of sorting.

why the sorting make it pass ?

People have designed the testcase to cause hash collision resulting in o(n^2). If you sort the array you get rid of the hash collision as elements are inserted in a different order, resulting in o(n).

Second and the usual, why for Cpp :

check the blog to make it o(n) instead of o(n^2) : https://codeforces.me/blog/entry/62393.

and Finally, i hope that i made you benefit.

thanks

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

interesting blog

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thx for your interest in clarifying this

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, today I solved these two problems:

Spoiler

Is this because there are no anti hash tests? I’m still unsure when to rely on the use of an unordered_map, unless one implement a pretty good hash function, are those solutions always hackable?

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

That was helpful. Thanks!

→ Reply