# RRJOKE - Editorial

Practice

Contest

Author: Roman Rubanenko

Tester: Tuan Anh

Editorialist: Florin Chirica

easy

none

### PROBLEM:

Find a permutation that minimize a certain function. Then, compress it and output the resulting number.

### QUICK EXPLANATION:

The problem is simple, after you notice the particularity of output.

### EXPLANATION:

What should be the solution for this task? Some optimized backtracking? 40 is too much! It must be some dynamic programming, but what states to keep? Itâs not so easy to find. Whatâs left? Do some sort of greedy! But how to find a greedy that passes all tests? Again, not so easy.

By now, I gave up solving the task.

Florin: Hey Roman, can you please give me a hint to solve RRJOKE? Iâm completely stuck.

Roman: yeeeaaahhh. Read the output section

Florin: Oh, I canât believe it. Youâre such a troll!

Letâs suppose somehow you calculated optimal permutation P (having elements P1, P2, âŚ, Pn). What you need to output is P1 xor P2 xor âŚ xor Pn. One can see âxorâ operation is commutative, so we can change the order of the numbers from permutation. Letâs sort the permutation. We get 1 2 3 âŚ N - 1 N. What we need to calculate? 1 xor 2 xor âŚ xor N - 1 xor N. Not sure if you feel this problem is a âGood Jokeâ if you fail to solve it in the contest, but I definitely enjoyed it. So, given N, you simply need to output 1 xor 2 âŚ xor N.

### AUTHORâS AND TESTERâS SOLUTIONS:

Authorâs solution
Testerâs Solution to be updated soon.

7 Likes

Wow this was an Awesome QUESTIONâŚ

The main focus point towards solving this problem is

"XOR" operation is commutative.

A very nice trick by the problem setter, at first it seemed too much, enjoyed it.

to problem setterâŚ(y) good joke dude

Now I realize, The joke (Title) was not related to the story (Problem), but [was related to] solving (Solution).

Seriously guys,it was great fun solving this problem,at first i didnât got any idea for solving this.Although i understood what it expects,then i noticed its accuracy was above 90% at that moment.I read it again,especially the output.Then,i got it :)Was truly a Good Joke! indeed,nice trick to make people think alotâŚ

how is (P1 xor P2 xor P3 xorâŚxor Pn) equal to (1 xor 2 xor 3âŚ xor N) ???

i actually found the correct permutation before taking xorâŚ* facepalm *

p1,p2,p3 are order in which you traverse the points.

indeed a good jokeâŚtook a long time to understand!!!

Epic troll, but nice problem (Y)

Haha really a nice editorial for an epic problem but can someone explain how do we really find the correct permutation ? @fauzdar65âŚplease elaborate

I know the solution to this problem was simple (really good joke :p) But i founded permutation and then calculated their XORâs and its showing correect output on pc and ideone but SHOWING WRONG ON CODECHEF!

here is link to my code:

http://codepaste.net/u9c86x

@sheru7
I dont understand ,why you trying to find permutation.
All permutation will produce same output(XOR is commutative).(1^2^3)==(3^1^2)==(1^3^2)
Simple two liner code.

for(i=1;i<=n;i++)

ans=ans^i;

void main()
{
int n;
cin>>n
int ans=1
for(int i=1;i<n;i++)
ans=ans^i;
}

Ahh! Now i realized the Joke. Thanks to Author of this editorial and Setter of Problem also. I came here after trying every solution which i can come up with.

Fantastic joke! Simply superb!

#include
using namespace std;

int main()
{
unsigned int n,r,a,b,j,t;
cin>>t;
while(tâ)
{
unsigned int r=0;
cin>>n;
for(j=1;j<=n;j++)
{
cin>>a;
cin>>b;
r ^= j;
}
cout<<r<<endl;
}
return 0;
}

This code is taking 5sec to execute. How can i reduce the time?

I feel so ashamed for asking this stupid questionâŚ I am a third year CS studentâŚ But, I feel that I donât even deserve to call myself thatâŚ

I have read the question n number of timesâŚ As soon as I read the question, I thought it is beyond my reachâŚ I couldnât even understand the question and I know I shouldnât have tried the Editorial before I even triedâŚ But, I was completely clueless about itâŚ

I expected that I could probably understand it better, if I could see the processâŚ But, the answer, instead of bringing me clarity, it only brought a sense of despair and hopelessnessâŚ

I understood that it is about finding the minimum distance between n points (whose x and y coordinates are given) lying on a planeâŚ And, I, also know that we need to XOR the n pointsâŚ But, I fail to see how it is related to XOR operation and what role does it play in finding the correct permutation(s)âŚ

Plus, the second test case has been a complete mysteryâŚ I know that I sound quite ridiculous and I know my comment has you guys thinking, âWhat an idiotâŚâ

I donât wish to see the solutionâŚ I only desire the to know process which is at workâŚ So, I could see where my logic failed meâŚ

So, I request that someone provides me with a more detailed explanationâŚ

@suyashd95

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.

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.

Got hint?

Well, I know you wouldnât, so let me tell you how the problem setter trolled us.

What is 2+3+5?

10âŚ

Ok, what is 3+2+5?

10 againâŚ

What is 5+3+2??

10 againâŚ

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. )

Lets re-arrange it-

Let p3+p5+4 =V
Since-

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-

p1+p2+p3+p4+p5

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