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.
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…
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
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…
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 :).
. I thought I could do a few contests since summer vacations means lot of free time but well, lets hope for the best :).