Lol, firstly no need to feel so down just because of this Q. Listen dude, this Q is VERY GOOD in hiding the real trick. The thing which this Q tested was apt/clever reading of Q, not your concepts of coding.
Ask yourself, “What is the question asking me?”
The question here says (or rather claims to) ask for the permutation of shortest path. But is it REALLY asking that?
The output says to print the XOR of the permutation you found.
Note 1- The permutation which we ‘found’ goes through all the points given, and is the shortest path.
The question now asks you to print the XOR of the permutation. Let me stress again, the permutation consists of/goes through all the points given in input.
Well, I know you wouldn’t, so let me tell you how the problem setter trolled us.
What is 2+3+5?
Ok, what is 3+2+5?
What is 5+3+2??
The question’s answer is also like that. The question asks us XOR of the permutation. And that permutation has all the points given in the input.
Meaning, speaking in more detail-
Let points given as input be p1, p2, p3 ,p4 ,p5.
Let Shortest permutation be p5, p4, p2, p1, p3.
What is the output asking us?
(Please assume that ‘+’ = XOR for below. )
Its asking for p5+p4+p2+p1+p3
Lets re-arrange it-
Let p3+p5+4 =V
V= p3+p5+p4 = p4+p5+p3 = p3+p4+p5 (meaning, any permutation of them are equal) &etc. we can re-arrange it in any way we want(since XOR is commutative).
[Please pay close attention to what I concluded above. if p3+p5+p4 is equal to V, then ANY combination of them is equal to V]
Now I think, you would agree that if we can re-arrange p5+p4+p2+p1+p3 in any way we want, then you will find that we can also re-arrange it as-
And this is nothing but the order of input given.
Infact, even order of input doesn’t matter. As i said with norma + operation, 2+3+5 is 10 in ANY order. Exact same rule applies to XOR also!
Meaning, once inputted all the points, all you need to return is the XOR of all the points. THATS ALL.
If the value of XOR of all points is V1, then it doesn’t matter what order you XOR’ed them, it doesn’t matter if the order you XOR’ed them is the ‘shortest path’ or any random combination, the value is SAME!
The problem setter trolled us by the fact that, while everyone was busy finding the shortest distance, many failed to realize that since 2+3+5 = 10 irrespective of permutation, the answer is actually just asking them the XOR of all the points in any combination possible.
Role of XOR-
The role of XOR is that, it is the thing which makes the Q a troll.
Had he actually asked the shortest permutation , the Q would have indeed been wayyy tougher.
And had the problem setter asked something like “Give the sum of X and Y co-ordinates of all points of shortest permutation which visits every point once” or something on that line, then everyone would have found the trick.
Since they used “XOR”, people weren’t able to see through the problem setter’s intention immediately. It took them a lot of ranting and head scratching (which must have highly amused the problem setter- I may remark!) before they were finally like “HOLYYY GODD! THE Q WAS JUST ASKING FOR…!!!”
Long story short- XOR was best option among available operators to misguide people. XD