KMXOR - Editorial (Unofficial) (As i know many of you were near to the solution and you r getting wrong answers)

editorial

#1

Hello Coders,

As I know many of you were near to solution but got wrong answers in this question. Here is my solution and you can even ask your doubts in your logic here…

Problem link :

Contest(div1)
Contest(div2)
Practice

Author : Yuri

DIFFICULTY: Easy

Short description of problem :

Making XOR of N elements as big as possible by using integers from 1 to K.

Explaination :

First of we need to know the most significant bit which is 1 in binary representation of number K (i.e. the first bit which is 1 from left side) .

This, can be done in many ways… simplest way is taking \lfloor log_2(k) \rfloor +1 (i.e. taking its floor function which is, obviously, typecasted to int)

Now we have the position of Most Significant Bit, starting from rightmost bit.

(Alternate: It can also be done by a for loop (hint : using k/=2 and k\%2 ) )

Now the MAX XOR value we can achieve in best possible case is all 1's till (and including) the most significant bit.

Example- If position was 3 then MAX XOR we can achieve is-

111_2 (in binary) == 7 in decimal.

So basically MAX XOR is nothing but {2}^{(p)}-1 where p is position of MSB from right (1-based indexing) .

Note that, there can’t be any 1 at left side of MSB (Most Significant Bit) in binary representation in any number 1 to K , else the number will become >K, violating the conditions.

Taking an example-

Click to view

Lets assume K to be 9 == 1001_2

then MAX XOR can be 1111_2 in binary… as simple as that…

In every case we can achieve the MAX XOR except some special cases like

1)N==1 (answer is K)

2)K==1 and N is even (answer is n times 1… hence XOR will be 0)

3)K==2 and N is odd ( answer is 2 followed by (N-1) times 1’s… where XOR would be 2)

Otherwise XOR of all can be achieved as all the number of bits counted are 1…

If your Output satisfies above explanation then your solution will definitely give AC

How to achieve MAX XOR for given N and K ?

Well there are many methods by which this can be done…

In fact only two numbers 1\leq number \leq K can achieve MAX XOR… and we can even make three numbers such that their XOR is the MAX XOR possible(i.e all 1's in binary).

Let me explain you how…

If K = 9 = 00001001_2
then find temp = 00001000_2 (keep every bit except the leftmost bit which is 1 in K as 0).

code for which would be…
temp = pow(2, (int) log2(k));

1) Achieving MAX XOR by using Two numbers less than k is …
temp \oplus temp-1 = 00001000_2 \oplus 00000111_2 = 00001111_2.

2) Achieving MAX XOR by using Three numbers less than k is …
temp \oplus temp-2 \oplus 1 = 00001000_2 \oplus 00000110_2 \oplus 00000001_2 = 00001111_2.

which are MAX XOR…

It is fact that if K>3

1 \leq temp , temp-1 , temp-2 \leq K (?Why… Think :D)

Now you might be thinking why we just found two ways of maxing the MAX XOR with Two and Three numbers…

Because that was the main solution… Let me Explain that…

Now as we know

y \oplus y = 0 and y \oplus 0 = y

which do you think is the number which all 1 to K will contain…( 1 itself isn’t it :D)

Two cases :

N is even :

print  
(temp-1)      (temp)      (1)      (1)      (1)... n terms     

N is odd :

print  
(temp-2)      (temp)      (1)      (1)      (1)... n terms       

Obviously Don’t print brackets…

So this is applicable when only K>3… (why not for k$\leq$3 ? take this as homework… :slight_smile: )

We had already discussed partial answer for k=1,2,3…

Lets complete them…

K==1

we don’t have any choice rather than printing 1’s …

K==2

print 2 followed by (N-1) times 1 … (why? think…)

K==3

N is odd : print 3 followed by (N-1) 1’s …
N is even : print 2 followed by (N-2) 1’s …

MY SOLUTION LINK:

Sample Solution


#2

My suggestion to people getting wrong answer is try this test case :
9
4 1
5 1
5 2
6 2
5 3
6 3
5 8
2 8
4 8
answer: XOR of all should be…
0
1
2
3
3
3
15
15
15

And don’t forget to check whether all are in range 1 to K…
And please do count numbers you are printing whether they are exactly N or not


#3

I am getting right in all the test cases mentioned above but still getting wrong answer https://ideone.com/4FqUwD


#4

corrected still getting wrong answer https://ideone.com/7192dd …sorry but please have a look at it…i have written the code neatly though


#5

I am getting right in all the test case mentioned above but still getting wa
https://ideone.com/3Et80h please have a look at it.


#6

Hey @l_returns ,

I went through your editorials, and edited the first half to what would seem ideal to me. You can refer to that, and then at the latter part of the editorial to check the differences, and note formatting syntax etc. :slight_smile:

Some things I would like to point out-

  1. I love your spirit of explanation. But it is an art to know when to explain very elaborately and when to refrain from that. What we call, Abstraction. :). I loved how you went on to tell the trick in detail, but at the same time, as you can see from editing history, I removed a bit of redundant explanations from the editorial. Too much of redundant explanation, where things are trivial bores the reader, and makes him feel as if editorialist is assuming him to be a kid/total-noob. Not to mention it unnecessarily makes the editorial lengthy!
  2. Formatting and presentation can be improved. Check out the format of latex etc. from the part I edited. :slight_smile:
  3. A few typos, but thats fine. Make sure there are no typos in headings.

Elaborating n point 1, even I did that when I wrote my very first unofficial editorial. I was a 2 star then, and was able to solve the question after looking at people’s code XD. Check it out here- https://discuss.codechef.com/questions/92733/feb-17-maketri-editorial-unofficial

See its such an extreme case of elaborate explanation! XD Criticthat editorial, see how it can be improved, and in the process see if you did that mistake as well! Thats all, I appreciate your sincere efforts :slight_smile:


#7

Can someone please tell me which test case fails for KMXOR for the following code?

It passes all the below mentioned test cases and I am still getting WA.

9

4 1

5 1

5 2

6 2

5 3

6 3

5 8

2 8

4 8


#8

nicely explained bro :slight_smile:


#9

Hello @L_returns could you please point out mistake in my logic

https://www.codechef.com/viewsolution/18617541


#10

https://www.codechef.com/viewsolution/18645512

What is wrong with this solution? Can you please help!


#11

hello @prnjl_rai

your code is giving wrong answer when ‘n’ is odd and k=3.
Add some more cases to it.


#12

So well explained… loved it! :slight_smile:


#13

This explanation is really helpful. This editorial is clearer than the Official one!


#14

link text

can someone help i got all test cases of above correct


#15

PS: sorry I saw the official editorial after I posted this one… Now I think I should let it be as maybe someone can get a help…


#16

Its my first attempt for writing editorial so please forgive me for my english and length of editorial…


#17

Thanks, I_returns. I almost solved the question just missed the edge cases! and lost 100 ratings got back to Div B :frowning:


#18

ohh… welcome :slight_smile:


#19

perfect, thanks for pointing out the edge cases. Finally got AC.


#20

welcome :slight_smile: