KMXOR - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

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.

2 Likes

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

The problem can be done like this also

1 Like

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

here I have my edited code… https://ideone.com/7192dd …i am still not able to solve the error to my problem

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

Click to view

4 1 1 2 1 8 4 4 8

Doesnt help? Send me your code so I can add more :slight_smile:

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

2 Likes

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

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

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

can anyone describe this editorial in brief please…

Can anyone tell whats wrong with my solution its getting WA https://www.codechef.com/viewsolution/18702042

1 Like

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

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

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

Nothing wrong with my solution still giving WA

https://www.codechef.com/submit/complete/20556327

I cannot understand what is wrong.

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

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…

solved… typecast output of power function…

1 Like

thanks mate!

1 Like

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…

1 Like

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

1 Like