×

# KMXOR - Editorial

Author: Yuri Shilyaev
Editorialist: Yury Shilyaev

Easy

# PREREQUISITES:

Xor operation, constructive.

# PROBLEM:

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.

# QUICK EXPLANATION:

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

# EXPLANATION:

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 AND TESTER'S SOLUTIONS:

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

This question is marked "community wiki".

18
accept rate: 0%

19.3k348495534

 2 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 - https://www.codechef.com/viewsolution/18611082 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 14.4k●1●13●52 accept rate: 18% 1 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) 1 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) Thanks... :) (21 May, 19:39) 1 missing Chef vijju's corner in editorials... (21 May, 19:41) 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) 2 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) 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) yeah people do tell they can't understand when code is more short, I agree... (21 May, 20:25) Can you suggest me something to improve my editorial ?? (21 May, 20:26) 1 Let me have a look. Will suggest if I find any :) (21 May, 20:28) okay thanks :) u ll cuz its my first attempt :D (21 May, 20:31) 1 Thank you so much @vijju123 ... It was a great help for me... :D (21 May, 21:13) 1 Happy to help bro :) (21 May, 21:34) showing 5 of 14 show all
 1 The problem can be done like this also https://letsdocp.wordpress.com/2018/05/21/codechef-problem-best-cake-ever/ answered 21 May, 13:35 3★vjvjain0 61●6 accept rate: 0%
 1 Can anyone tell whats wrong with my solution its getting WA https://www.codechef.com/viewsolution/18702042 answered 30 May, 22:03 11●1 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) 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) your logic and output seems correct... dk what does codechef found wrong :( (01 Jun, 19:47)
 0 I am not able to understand the error in my solution.. the code is given in the link below https://ideone.com/4FqUwD answered 21 May, 13:24 11●2 accept rate: 0%
 0 I did the same solution... I tried to explain this in bit detail... link to my unofficial editorial... answered 21 May, 14:00 1.1k●1●8 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) 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)
 0 here I have my edited code... https://ideone.com/7192dd .....i am still not able to solve the error to my problem answered 21 May, 14:46 11●2 accept rate: 0% 1 solved.. typecast output of power function.... (21 May, 15:31) 1 thanks mate! (21 May, 15:56)
 0 Can someone please provide a test case that fails? 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 answered 22 May, 08:14 25●2 accept rate: 14% Will reply u on ur comment on my editorial shortly.. (22 May, 09:47) alright! will wait. Thankyou. :) (22 May, 09:49) Well thank me if I solve it :) (22 May, 09:51) solved... keeping k==1 k==2 and k==3 condition before n==2 helps... (because 2 1 test case failed..) (22 May, 10:21)
 0 whats wrong in my solution .... someone plz help thnx in advance.... https://www.codechef.com/viewsolution/18638067 answered 24 May, 01:42 1 accept rate: 0% try this test case and do let me know if there wasn't any mistake... (25 May, 01:28) all above test cases pass .. plz if possible check for once ..... I even type-casted pow function value to long long .... https://www.codechef.com/viewsolution/18651992 thnx in advance ... (26 May, 07:17) this is the edited one with minor changes ..... plz see whats the mistake i am getting WA ...... https://www.codechef.com/viewsolution/18652030 (26 May, 07:38) Okay bro you do have read above answer.. that's nice.. let me check.. (26 May, 10:07) i have further modified the code .... plz check ..... .... https://www.codechef.com/viewsolution/18676006..... i have got many WA .... ... plz help ...... thnx in advance !!! (27 May, 14:32)
 0 can anyone describe this editorial in brief please...... answered 26 May, 23:17 59●4 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)

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

537
accept rate: 0%

# HERE

(14 Jun, 01:18)
 0 Hi, I am getting wrong answer for the following problem. https://www.codechef.com/problems/KMXOR My solution : https://www.codechef.com/viewsolution/19707356 can someone please tell what is wrong in my solution? Thanks answered 13 Aug, 14:22 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×280
×161
×55