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.
Auto comment: topic has been translated by elnazar (original revision, translated revision, compare)
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)
Yes, I am using python's defaultdict wich shares similarities with unuordered_map. Yeah I got the issue and found answer i guess.
some_randintprevents 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)
Thank you! I got it.