Optimal Xor Set OPTSET SOLUTION

by

Optimal Xor Set OPTSET

Find K distinct numbers in the range [1,N] such that the bitwise XOR of all the numbers is maximized. Print any set of these numbers that maximize the XOR.

Input
The first line contains an integer T, the number of test cases. Then the test cases follow.
Each test case contains a single line of input, two integers N, K.
Output
For each test case, output K distinct integers in any order as described in the problem.

Constraints
1≤T≤104
1≤K≤N≤106
The sum of N over all queries is at most 4⋅106.
The sum of K over all queries is at most 2⋅106.
Subtasks
Subtask #1 (5 points):

1≤T≤50
1≤K≤N≤20
Subtask #2 (20 points):

1≤T≤50
1≤K≤N≤200
The sum of N over all queries is at most 800.
The sum of K over all queries is at most 400.
Subtask #3 (75 points): original constraints

Sample Input
3
10 1
9 2
8 7
Sample Output
10
7 8
1 2 3 4 5 6 8
Explanation
Test Case 1: The only possible set is {10} which gives the value 10.

Test Case 2: The other possible set is {9,6} which gives the value 9⊕6=15=7⊕8.

Test Case 3: The only possible set is {1,2,3,4,5,6,8} which gives the value 1⊕2⊕3⊕4⊕5⊕6⊕8=15.

Program:

#include <algorithm>
#include <string>
#include <bits/stdc++.h>
#include<cmath>
using namespace std;
 
int main(){
    int t; cin >> t;
    while (t--){
        int n,k; cin >> n >> k;
        
        int maxsum = int(log2(n)) + 1;
        int ans = pow(2,maxsum) - 1;


        string str;
        for(int i = 0; i < k; i++){
            str.push_back('1');
        }
        for(int i = k; i < n; i++){
            str.push_back('0');
        }
  
        sort(str.begin(),str.end());
        string ansone = str;
        int ansss = -1;

        
        while(true){
            
            int xorans = 0;
            for(int i = 0; i < str.size(); i++){
           
                if(str[i] == '1'){
                    xorans = xorans^(i+1);
                }
            }
            if(xorans > ansss){
                ansss = xorans;
                ansone = str;
            }

            if(xorans == ans){
                break;
            }
            if(next_permutation(str.begin(), str.end()) == false){
                break;
            }
        }
   
        for(int i = 0; i < ansone.size(); i++){
            if(ansone[i] == '1'){
                cout << i+1 << " ";
            }
        }
        cout << "\n" ;
    

    }

    return 0;
}

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :