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.
3 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… 7192dd - Online C++ Compiler & Debugging Tool - Ideone.com …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
Also, if you’d want to see my solution - CodeChef: Practical coding for everyone
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 CodeChef: Practical coding for everyone
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.
My solution : CodeChef: Practical coding for everyone
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
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
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
1 Like