You are not logged in. Please login at to post your questions!


KMXOR - Editorial



Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev




Xor operation, constructive.


You are given two integers $N$ and $K$. Your task is to construct a sequence $g_1, \dots, g_N$, that $1 \le g_i \le K$ for all $i$ and $g_1 \oplus g_2 \oplus \cdots \oplus g_N$ is maximum possible.


Let $m$ be the maximum integer that $2^m \le K$. The maximum possible answer is somewhere near $2^{m + 1} - 1$.


Let's first print $2^m$ and $2^m - 1$. This numbers give xor $2^{m + 1} - 1$. Now, if let's complete the sequence with ones. The xor would not change if $N$ is even, otherwise, let's swap $2^m - 1$ we added with $2^m - 2$.

Of course, we should also consider some corner cases, on which our solution doesn't work. They are $N = 1; K = 1; K = 2; K = 3$.


Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 20 May, 20:54

hloya_ygrt's gravatar image

accept rate: 0%

edited 21 May, 17:28

admin's gravatar image

0★admin ♦♦

One of the useful cases- try it if you decide to give up debugging after hours and hours-

View Content

Also, if you'd want to see my solution -

The only case handling done is for $K=1$ (is it redundant? Try and find out!) , and if number of $1's$ to be added is even or odd. No other specific edge case handling was needed in my approach.

Its based on adding $K$ first, and then adding a number $X$ such that $K \oplus X={2}^{a}-1$ where $a$ is number of bits in binary representation of $K$ . Rest of places were filled with $1's$ with special handling if number of $1's$ turns out to be odd making maximum value ${2}^{a}-2$


answered 21 May, 19:16

vijju123's gravatar image

5★vijju123 ♦
accept rate: 19%

edited 21 May, 19:40


how to add this view content and hide content @vijju123 ... I wanted to make this type thing for test case in my editorial but didn't knew how to add that.... thanks...

(21 May, 19:21) l_returns3★

Keep the content to be hidden in between [@hide] [@/hide] . (Remove the @ signs for it to work)

If there still exists any issue, ping me, I will mail you a screenshot :)

(21 May, 19:33) vijju123 ♦5★

Thanks... :)

(21 May, 19:39) l_returns3★

missing Chef vijju's corner in editorials...

(21 May, 19:41) l_returns3★

I used the same idea of choosing K and then some other combination of values :D
The code can be made much shorter though: 18623918

(21 May, 19:47) meooow ♦6★

haha what a short code @meooow ...
and python is also very much useful...

(21 May, 19:50) l_returns3★

You dont know how happy that makes me feel <33333333333

Sadly, I dont think I would be getting any slot for editorials till August :( . I thought I could do a few contests since summer vacations means lot of free time but well, lets hope for the best :).

(21 May, 19:51) vijju123 ♦5★

When writing my code I am more focused on

"Ok , what does this part do? What guarantees correctness of concept? What guarantees correctness of implementation?"

So I elaborately write it. And people complain that they cant understand what I'm doing when I write shorter ones XD

(21 May, 20:19) vijju123 ♦5★

yeah people do tell they can't understand when code is more short, I agree...

(21 May, 20:25) l_returns3★

Can you suggest me something to improve my editorial ??

(21 May, 20:26) l_returns3★

Let me have a look. Will suggest if I find any :)

(21 May, 20:28) vijju123 ♦5★

okay thanks :)
u ll cuz its my first attempt :D

(21 May, 20:31) l_returns3★

Thank you so much @vijju123 ...
It was a great help for me... :D

(21 May, 21:13) l_returns3★

Happy to help bro :)

(21 May, 21:34) vijju123 ♦5★
showing 5 of 14 show all

answered 21 May, 13:35

vjvjain0's gravatar image

accept rate: 0%

Can anyone tell whats wrong with my solution its getting WA


answered 30 May, 22:03

gautam1212's gravatar image

accept rate: 0%

try this test case and have a look at editorial(unofficial) if u r not missing anything(specially corner cases that I mentioned)...

(31 May, 00:14) l_returns3★

I m getting right answers in all the test cases mentioned above.Please have a look. 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 1 3 1 1 1 1 2 1 1 1 1 1 1 2 12 1 1 8 7 8 7 1 1

(01 Jun, 17:44) gautam12123★

your logic and output seems correct... dk what does codechef found wrong :(

(01 Jun, 19:47) l_returns3★

I am not able to understand the error in my solution.. the code is given in the link below


answered 21 May, 13:24

sharpowl_06's gravatar image

accept rate: 0%

I did the same solution... I tried to explain this in bit detail... link to my unofficial editorial...


answered 21 May, 14:00

l_returns's gravatar image

accept rate: 27%

try this test case and do let me know if there wasn't any mistake and i can try to help u...

(21 May, 14:21) l_returns3★

FOR people getting wrong answer and not able to find their mistake after try for hours.. though i suggest that u should try to solve it by your own.. that the purpose of competitive coding..

(21 May, 14:22) l_returns3★

here I have my edited code... .....i am still not able to solve the error to my problem


answered 21 May, 14:46

sharpowl_06's gravatar image

accept rate: 0%


solved.. typecast output of power function....

(21 May, 15:31) l_returns3★

thanks mate!

(21 May, 15:56) sharpowl_062★

Can someone please provide a test case that fails?

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


4 1

5 1

5 2

6 2

5 3

6 3

5 8

2 8

4 8


answered 22 May, 08:14

thecodearrow's gravatar image

accept rate: 0%

Will reply u on ur comment on my editorial shortly..

(22 May, 09:47) l_returns3★

alright! will wait. Thankyou. :)

(22 May, 09:49) thecodearrow3★

Well thank me if I solve it :)

(22 May, 09:51) l_returns3★

solved... keeping k==1 k==2 and k==3 condition before n==2 helps... (because 2 1 test case failed..)

(22 May, 10:21) l_returns3★

whats wrong in my solution .... someone plz help thnx in advance....


answered 24 May, 01:42

codes_do_speak's gravatar image

accept rate: 0%

try this test case and do let me know if there wasn't any mistake...

(25 May, 01:28) l_returns3★

all above test cases pass .. plz if possible check for once ..... I even type-casted pow function value to long long ....

thnx in advance ...

(26 May, 07:17) codes_do_speak0★

this is the edited one with minor changes ..... plz see whats the mistake i am getting WA ......

(26 May, 07:38) codes_do_speak0★

Okay bro you do have read above answer.. that's nice.. let me check..

(26 May, 10:07) l_returns3★

i have further modified the code .... plz check ..... .... i have got many WA .... ... plz help ...... thnx in advance !!!

(27 May, 14:32) codes_do_speak0★

can anyone describe this editorial in brief please......


answered 26 May, 23:17

code__champ's gravatar image

accept rate: 0%

HERE is my unofficial editorial(I have described whole soln there)
my solution was almost same as this editorial soln...

(28 May, 03:22) l_returns3★

Please write Editorials in such a way so that a beginner like me can easily understand the explaination. Codechef should look into this matter.


answered 13 Jun, 22:01

osho_garg's gravatar image

accept rate: 0%

post queries about what you didn't understood in editorials... and also you can have a look at my editorial for this question


(14 Jun, 01:18) l_returns3★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 20 May, 20:54

question was seen: 1,797 times

last updated: 14 Jun, 01:18