elnazar's blog

Why Does XOR Make a Difference in Performance?
By elnazar, history, 21 hour(s) ago, translation, In English

Recently, I faced with one issue where two seemingly similar solutions performed differently. I want to know why it is happening?

Code 1: Used an XOR operation (num ^ some_randint) to preprocess numbers before counting their frequencies

Code 2: Counted numbers directly without any transformation.

Both codec followed identical logic after this step, but code 1 passed the test cases efficiently, while code 2 gotaTLE.

WHY? I would be happy if someone could explain.

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

»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by elnazar (original revision, translated revision, compare)

→ Reply
»
20 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Are you counting frequency with unordered_map? You’re probably facing a hashing collision attack and the xor helps avoid it (although one could theoretically hack it during contest)

→ Reply
  • »
    »
    19 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I am using python's defaultdict wich shares similarities with unuordered_map. Yeah I got the issue and found answer i guess.

    → Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

some_randint prevents the hack of your dictionnary by xoring the values to a random value only the program running can know which prevents any melicious testcases from hacking your dictionnary and also any one trying to hack you because it's a random number.

you can read more about it here (c++ unorderedmap is similar to python dictionaries)

→ Reply