Optimal Xor Set Editorial

general
, , ,
1

Can someone explain how to solve this question or link to a similar problem or some source to study about it please… I managed to pass first subtask using recursion

2

First you can arrive to the fact that maximum xor of numbers between 1 to N is achieved when all the bits in N are set. Lets denote this xor as X. It can be proved that X can always be made by choosing K numbers from 1 to N (except when K : (N , N - 1,1)). Now problem is changed to choosing K integers from 1 to N such that xor is X.
Note that X can be easily made by choosing only two numbers.

A = max ( 2^i \leq N )
B = A - 1
C = A - 2
Now , A xor B = X , A xor C = X - 1

First choose K - 2 integers from 1 to N (expect A , B , C) such that their xor is either 1 or 0.
Which can be easily achieved by choosing consecutive integers of the form (2*n , 2*n + 1).
if xor of K - 2 integers is 0 ,select A and B such that resulting xor is (0 xor A xor B) = X
if xor of K - 2 integers is 1, select A and C such that resulting xor is (1 xor A xor C)= X
So in both the cases we can choose (K - 2 + 1 + 1 == K) integers such that the max xor X is achievable.

Just considering the case when,
K = 1 , answer would be N
K = N , answer would be 1 to N
K = N - 1 , we could greedly leave any one integer Y such that resulting xor is as maximum as possible.

5 Likes
3

Bro can u give me ur discord id

5

dhanyavad bro

1 Like
6

Hi! I tried out the solution you have mentioned, (or atleast what I understood of it), it is giving TLE, Pls check it out CodeChef: Practical coding for everyone .
P.S Sorry for so many if/else loops

7
  • TLE is just because you aren’t incrementing i in line 116 and 127.
  • Also to avoid corner cases for very small N I used simple naive solution. Otherwise you can consider making another if else ladder for such N.
8

I have incremented i in line 122 and 133 inside the loops, it works fine for sample inputs as well

9

Try :-
1
15 8

10

WHY IS IT TLE’ing??? Do I need to give a brute force solution upto like n ~ 20?

11

Not always, consider the following test cases:

Test case 1 
1
6 4
Test case 2 
1
14 12

The XOR here can be atmost N and the correct statement would be that we can always construct either N or X.

1 Like
12

Yes , I indeed skipped mentioning various corner cases. This is a explanation of my solution for every N and K but it gives an idea that X can be made for every ( 2 \leq K \leq N - 3) and if not we could reach N as you mentioned.

13

No , you are missing to increment i and adding continue this would cause a TLE.

14

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

can you help me why my code is failing
i have seprated case for k = n, k = 1, k = 2
for case like 6 4 i have printed all numbers less than 4 and in the end i have added 6 so that max xor will be 6

15

I recommend that you run many cases with random data for N and K where 2 <= K < N. In each case evaluate the target = (1 << Q) - 1 where Q is the smallest power of 2 larger than N, and see how much short of the target your solution is. The solution should reach the target in almost all cases: in those cases where it does not you can check carefully to see what is happening.