RRJOKE - Editorial

general
, ,
1

PROBLEM LINK:

Practice

Contest

Author: Roman Rubanenko

Tester: Tuan Anh

Editorialist: Florin Chirica

DIFFICULTY:

easy

PREREQUISITES:

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 :slight_smile:

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.

17 Likes
2

Wow this was an Awesome QUESTION…

4 Likes
3

to problem setter…(y) good joke dude :smiley:

3 Likes
4

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

Good sense of humor, @admin. :slight_smile:

3 Likes
5

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… :slight_smile:

2 Likes
6

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

7

i actually found the correct permutation before taking xor…* facepalm *

8

indeed a good joke…took a long time to understand!!!

2 Likes
9

Epic troll, but nice problem (Y)

2 Likes
10

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

11

I need help please!

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

12

@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;

13

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

14

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.

1 Like
15

Fantastic joke! Simply superb!

1 Like
16

#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?

17

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…’

But, I also know that CS community is all about helping and assisting others… So, please help me in solving my doubts…

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…

2 Likes
18

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

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.

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

Its asking for p5+p4+p2+p1+p3

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

8 Likes
19

@vijju123 First of all, thank you for so much answering my questions… Thankfully, I got my groove back after writing my question by listening to Kishore Kumar’s hits as well as solving a couple of other practice questions…

Your explanation was absolutely wonderful and it cleared all of my misconceptions and doubts regarding this fantastic question…

Even though, I am sure that my doubts are all gone… Yet, to verify, that I am finally thinking along the correct lines, I am putting forward my own test case…

Input:
4
2 3
1 2
9 0
0 0

In the above input, the only thing which matters is the number of points which, in the above case is, 4.

The coordinates of individual points really does not count, since they are present to confuse us… Hence, they do not play any role in the algorithm to find the correct answer. So, we can safely ignore them.

Output:
4

The answer is based on the fact that final answer (A)= 1 XOR 2 XOR 3 XOR 4 = 4. It is based on the fact that we have marked each point in a sequential order. Hence:

2 3 -> 1
1 2 -> 2
9 0 -> 3
0 0 -> 4

Multiple permutations can exist which will lead to shortest path, like [1, 2, 3, 4], [2, 3, 4, 1], [3, 4, 1, 2], [4, 3, 2, 1]… Each permutation will end up having the same result since XOR operation is commutative in nature.

So, coming to the final output…

We can easily calculate the final answer by XORing each mark i.e, equation A.

Steps:

  1. Initially, A = 1 (Since, 0 XOR 1 = 1)
  2. A = 1 XOR 2 = 3
  3. A = 3 XOR 3 = 0
  4. A = 0 XOR 4 = 4

Hence, the final output: 4… Please do me a favor and tell me whether my output is indeed the right one depending on my input…

2 Likes
20

Your final ans is correct. You got permutation thing right. If you notice closely, we can always generalise answer as-

“XOR of all Natural numbers till n”

Ie- 1 xor 2 xor 3…(n-1) xor n

And i think you can implement this now. I am glad tgat my explanation helped :slight_smile:

2 Likes