You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 20 May, 20:54

hloya_ygrt's gravatar image

3★hloya_ygrt
17
accept rate: 0%

edited 21 May, 17:28

admin's gravatar image

0★admin ♦♦
19.0k348495531


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$

link

answered 21 May, 19:16

vijju123's gravatar image

5★vijju123 ♦
13.6k11036
accept rate: 19%

edited 21 May, 19:40

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) l_returns3★
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) vijju123 ♦5★

Thanks... :)

(21 May, 19:39) l_returns3★
1

missing Chef vijju's corner in editorials...

(21 May, 19:41) l_returns3★

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) l_returns3★
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) vijju123 ♦5★

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) vijju123 ♦5★

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

(21 May, 20:25) l_returns3★

Can you suggest me something to improve my editorial ??

(21 May, 20:26) l_returns3★
1

Let me have a look. Will suggest if I find any :)

(21 May, 20:28) vijju123 ♦5★

okay thanks :)
u ll cuz its my first attempt :D

(21 May, 20:31) l_returns3★
1

Thank you so much @vijju123 ...
It was a great help for me... :D

(21 May, 21:13) l_returns3★
1

Happy to help bro :)

(21 May, 21:34) vijju123 ♦5★
showing 5 of 14 show all
link

answered 21 May, 13:35

vjvjain0's gravatar image

3★vjvjain0
213
accept rate: 0%

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

link

answered 30 May, 22:03

gautam1212's gravatar image

3★gautam1212
111
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) l_returns3★

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) gautam12123★

your logic and output seems correct... dk what does codechef found wrong :(

(01 Jun, 19:47) l_returns3★

I am not able to understand the error in my solution.. the code is given in the link below https://ideone.com/4FqUwD

link

answered 21 May, 13:24

sharpowl_06's gravatar image

2★sharpowl_06
11
accept rate: 0%

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

link

answered 21 May, 14:00

l_returns's gravatar image

3★l_returns
77018
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) l_returns3★

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) l_returns3★

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

link

answered 21 May, 14:46

sharpowl_06's gravatar image

2★sharpowl_06
11
accept rate: 0%

1

solved.. typecast output of power function....

(21 May, 15:31) l_returns3★
1

thanks mate!

(21 May, 15:56) sharpowl_062★

Can someone please provide a test case that fails?

https://gist.github.com/thecodearrow/d08e3677df05281cf42213147fa89c07#file-kmxor-py

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

link

answered 22 May, 08:14

thecodearrow's gravatar image

3★thecodearrow
91
accept rate: 0%

Will reply u on ur comment on my editorial shortly..

(22 May, 09:47) l_returns3★

alright! will wait. Thankyou. :)

(22 May, 09:49) thecodearrow3★

Well thank me if I solve it :)

(22 May, 09:51) l_returns3★

solved... keeping k==1 k==2 and k==3 condition before n==2 helps... (because 2 1 test case failed..)

(22 May, 10:21) l_returns3★

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

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

link

answered 24 May, 01:42

codes_do_speak's gravatar image

0★codes_do_speak
1
accept rate: 0%

try this test case and do let me know if there wasn't any mistake...

(25 May, 01:28) l_returns3★

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) codes_do_speak0★

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) codes_do_speak0★

Okay bro you do have read above answer.. that's nice.. let me check..

(26 May, 10:07) l_returns3★

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) codes_do_speak0★

can anyone describe this editorial in brief please......

link

answered 26 May, 23:17

code__champ's gravatar image

2★code__champ
594
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) l_returns3★

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

link

answered 13 Jun, 22:01

osho_garg's gravatar image

1★osho_garg
1
accept rate: 0%

post queries about what you didn't understood in editorials... and also you can have a look at my editorial for this question

HERE

(14 Jun, 01:18) l_returns3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×255
×150
×55

question asked: 20 May, 20:54

question was seen: 1,797 times

last updated: 14 Jun, 01:18