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…

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…

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

solved… typecast output of power function…

1 Like

thanks mate!

1 Like

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

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

Thanks… :slight_smile:

missing Chef vijju’s corner in editorials…

1 Like

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

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

You dont know how happy that makes me feel <33333333333

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

2 Likes

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

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

Can you suggest me something to improve my editorial ??

//