PROBLEM LINK:
Setter: Abhinav sharma
Tester: Samarth Gupta
Editorialist: Ajit Sharma Kasturi
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
An array A of size N is called an interesting array if N \geq 1 and A_i = 2^x -1 for some integer
1 \leq x \leq 60. We need to find one such interesting array with minimum size where the bitwise xor
of all the elements in the array is C.
EXPLANATION:
First let us analyse the binary representation of 2^x -1 . It is 1111\dots ( x times ).
Therefore, intuition suggests us that this problem can be solved constructively as follows:
Let us take an initial empty array arr and also keep track of a variable cur which denotes the current xor of all the elements of arr.
(In the below method the word positon has 0-based indexing ).
Now iterate over i from 60 to 0:
-
If both bits in cur and C at position i are the same i.e either both are set or both are unset, we need not apply any operation and continue to next i.
-
Else we need to add an element to the array in order to change to toggle the bit at position i for cur. Since we can add only numbers of the form 2^x -1, we will add 2^{i+1} - 1 to arr and update cur as cur = cur \oplus (2^{i+1} -1).
After this entire procedure is done, there is one special case left to handle. What if C =0 \hspace{1 mm} ? Then, we will end up with an empty array arr. But an interesting array must have size N \geq 1. Here, we canβt have one element with cur =0 since 2^x -1 \gt 0 for 1 \leq x \leq 60. Therefore, in this special case, we need to add any two equal elements of the form 2^x -1, (for example 1, 1) to arr.
Now, we can output the final array arr along with its size.
TIME COMPLEXITY:
O(60) for each testcase.
SOLUTION:
Editorialist's solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main()
{
int tests;
cin >> tests;
while (tests--)
{
ll C;
cin >> C;
ll cur_xor = 0;
vector<ll> arr;
for (int i = 60; i >= 0; i--)
{
ll bit1 = (1ll << i) & cur_xor;
ll bit2 = (1ll << i) & C;
if (bit1 != bit2)
{
arr.push_back((1ll << (i + 1)) - 1);
cur_xor ^= (1ll << (i + 1)) - 1;
}
}
if (arr.empty())
arr = {1, 1};
cout << arr.size() << endl;
for (int i = 0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << endl;
}
return 0;
}
Setter's solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
ll sum = 0;
cin >> T;
while(T--){
ll c;
cin>>c;
if(c==0){
cout<<2<<el<<"1 1"<<el;
}
else{
int prev = -1;
ll b=0;
vector<ll> v;
ll c1=c;
while(c){
if((c&1)!=prev){
if(prev!=-1) v.pb((1ll<<b)-1);
prev = (c&1);
}
c>>=1;
b++;
}
v.pb((1ll<<b)-1);
sum+=v.size();
cout<<v.size()<<el;
for(auto h:v) cout<<h<<" ";
cout<<el;
ll xr = 0;
for(auto h:v){
xr^=h;
//assert(h>0 && h<(1ll<<60) && __builtin_popcountll(h+1)==1);
}
//assert(xr==c1);
}
}
cerr<<sum<<el;
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
Tester's solution
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
return readString(l,r,' ');
}
void readEOF(){
assert(getchar()==EOF);
}
long long pws[61];
void pre(){
pws[0] = 1;
for(int i = 1 ; i <= 60 ; i++)
pws[i] = pws[i-1]*2;
}
vector<int> dig(long long x){
vector<int> vec;
while(x)
vec.push_back(x%2), x /= 2;
return vec;
}
vector<long long> solve(vector<int> dig){
vector<long long> ans;
ans.push_back(pws[dig.size()] - 1);
int f = 1;
while(dig.size()){
if(dig.back() == f)
dig.pop_back();
else{
ans.push_back(pws[dig.size()] - 1), f = 1 - f;
}
}
return ans;
}
int solve(long long x){
if(x == 0)
return 0;
int ans = solve(x/2);
return (ans + (ans + x)%2);
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
t = readIntLn(1, 1e5);
int sum = 0;
pre();
while(t--){
long long x = readIntLn(0, (1ll << 60) - 1);
if(x == 0){
sum += 2;
assert(sum <= 1e6);
cout << 2 << '\n';
cout << "3 3" << '\n';
continue;
}
vector<long long> ans = solve(dig(x));
int count = solve(x);
assert(ans.size() == count);
long long j = 0;
for(auto ele : ans)
j ^= ele;
assert(j == x);
sum += count;
assert(sum <= 1e6);
cout << count << '\n';
for(auto j : ans)
cout << j << " ";
cout << '\n';
}
readEOF();
return 0;
}
Please comment below if you have any questions, alternate solutions, or suggestions.