PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setters: Tejas Pandey,Utkarsh Gupta
Tester: Manan Grover, Abhinav Sharma
Editorialist: Devendra Singh
DIFFICULTY:
2543
PREREQUISITES:
PROBLEM:
Chef has an array A of length N such that A_i = i.
In one operation, Chef can pick any two elements of the array, delete them from A, and append either their bitwise XOR or their bitwise OR to A.
Note that after each operation, the length of the array decreases by 1.
Let F be the final number obtained after N-1 operations are made. You are given an integer X, determine if you can get F=X via some sequence of operations.
In case it is possible to get F = X, print the operations too (see the section Output format for more details), otherwise print -1.
EXPLANATION:
Let us handle the case when N=2 separately, when N is 2 only possible value of X is 3 as both XOR
and OR
of 1 and 2 result in 3. So if N is 2 and x!=3, answer is -1 otherwise both XOR
or OR
of 1 and 2 are acceptable answers.
If some bit in X is set to 1 which is not set to 1 in any number till N then there is no possible way to attain such X , Hence answer in this case is -1 too.
If N is a power of two then the most significant bit in N is set to 1 in only one number and is 0 in all other numbers less than N hence whether you take XOR
with this number or OR
with this number, this bit has to be set to 1 in X . If it is unset in X then the answer is -1
Otherwise it is always possible to construct the answer:
Consider the construction take OR
of all the elements in the array which are not a power of 2.
This way at least all the bits upto most significant bit of N( excluding it) will be set in the the number obtained.
Proof
If N is a power of 2.Then since we take OR
with (2^{msb})-1. It sets all the bits upto msb of N in the number obtained.
Otherwise we take OR
of N with 2^{msb}-1 and this sets all the bits upto msb of N in the number obtained.
Now iterate on the bits from i=0 to the most significant bit of N. If it is set in X we take OR
with 2^i present in the array otherwise we take XOR
with 2^i present in the array.
(Since if N is a power of 2 then X will have most significant bit of N set, therefore we will take OR with N in the end.)
Thus we can get the final value same as X by this method.
TIME COMPLEXITY:
O(N) or O(Nlog(N)) depending upon implementation for each test case.
SOLUTION:
Setter's solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n, x;
cin >> n >> x;
int bk = 0;
for(int i = 20; i > 0; i--) {
if(n&(1LL<<i)) {
bk = (1LL<<(i + 1));
break;
}
}
if((n == 2 && x != 3) || ((n&(n - 1)) == 0 && (x&n) == 0) || x >= bk) {
cout << "-1\n";
continue;
}
if(n == 2) {
cout << "1 1 2\n";
continue;
}
set<int> s1, s2;
for(int i = 1; i <= n; i++) s1.insert(i);
for(int i = 0; i < 20; i++) {
if((1LL<<i) > n) break;
if((x&(1LL<<i)) == 0) {
s1.erase((1LL<<i));
s2.insert((1LL<<i));
}
}
int n1 = 0, n2 = 0;
if(s1.size()) {
n1 = (*(s1.begin()));
s1.erase(s1.begin());
while(s1.size()) {
int now = (*(s1.begin()));
cout << "1 " << n1 << " " << now << "\n";
n1 |= now;
s1.erase(s1.begin());
}
}
if(s2.size()) {
n2 = (*(s2.begin()));
s2.erase(s2.begin());
while(s2.size()) {
int now = (*(s2.begin()));
cout << "1 " << n2 << " " << now << "\n";
n2 |= now;
s2.erase(s2.begin());
}
}
if(n1 > 0 && n2 > 0) cout << "2 " << n1 << " " << n2 << "\n";
}
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
int n, x, msbx, msbn;
cin >> n >> x;
map<int, bool> ispow2;
if (n == 2 && x != 3)
{
cout << -1 << '\n';
return;
}
else if(n==2 && x==3)
{
cout<<1<<' '<<1<<' '<<2<<'\n';
return ;
}
for (int i = 0; i < 20; i++)
{
ispow2[1 << i] = true;
if ((1 << i) & n)
msbn = i;
if ((1 << i) & x)
msbx = i;
}
if (msbx > msbn)
{
cout << -1 << '\n';
return;
}
if (!ispow2[n] || (x & n))
{
int val = 0;
for (int i = 1; i <= n; i++)
{
if (!ispow2[i])
{
if (i > 3)
cout << 1 << ' ' << i << ' ' << val << '\n';
val |= i;
}
}
for (auto y : ispow2)
{
if (y.F > n || !y.S)
continue;
if (x & (y.F))
{
cout << 1 << ' ' << y.F << ' ' << val << '\n';
val |= y.F;
}
else
{
cout << 2 << ' ' << y.F << ' ' << val << '\n';
val ^= y.F;
}
}
}
else
{
cout << -1 << '\n';
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}