PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: kingmessi
Tester: watoac2001
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given N and S, construct an array of length N containing positive integers, such that its sum is S and bitwise XOR is 0.
EXPLANATION:
The bitwise XOR of the array being 0 means that each bit must occur in an even number of elements.
In particular, the lowest bit must occur in an even number of elements; which means that the sum of the array must be even (since the lowest bit will appear an even number of times).
So, if S is odd, no solution can exist.
Also, every element being positive means that the sum of the array should be at least N; so if S\lt N again no solution can exist.
If N is even, there’s now a relatively simple solution: if we can write \frac{S}{2} as the sum of \frac{N}{2} positive integers, we can simply duplicate this to obtain an array of length N with sum S and xor 0.
This is because x\oplus x = 0 for any integer x, so if every element is duplicated the overall xor must be 0.
Writing \frac{S}{2} as the sum of \frac{N}{2} integers is quite simple, since we ensured S\geq N.
For example, just take \frac{N}{2} - 1 occurrences of 1, and one occurrence of \frac{S}{2} - \frac{N}{2} + 1.
When N is odd, however, a bit more thought is needed.
First off, when N is “large enough”, we can infact use the same idea behind the solution for even N.
That is, start out with [1, 2, 3], then obtain a sum of S-6 using the remaining N-3 positions.
N-3 and S-6 are both even, so this works - as long as S-6\geq N-3, of course.
When S-6\lt N-3, no solution exists.
Why?
The XOR must be 0, so every bit should occur an even number of times.
This means we can’t have every element be 1, unlike the even case.
So, some power of 2 higher than 1 should appear at least twice.
This gives us the minimum possible sum of the array to be 2^1 + 2^1 + 2^0\cdot (N-1), by having 2^1 appear twice and 2^0 appear N-1 times (to ensure that everything is positive).
This is N-1+4 = N+3.
So, if S\lt N+3 no solution exists; which is equivalent to saying S-6\lt N-3 (by subtracting 6 from both sides).
Notice that this solution works for all N\geq 5.
That leaves us with N = 1 and N=3 to take care of.
If N = 1, no solution exists.
If N = 3, we need a different approach.
We want to find three integers x, y, z such that x+y+z = S, and x\oplus y\oplus z = 0.
In a bit of wishful thinking, it’d be nice if we could choose x = \frac{S}{2}, and pick y and z appropriately.
Indeed, if \frac{S}{2} has at least two different set bits, this is always possible: choose x = \frac{S}{2}, then give some of the set bits of \frac{S}{2} to y and the others to z.
This will ensure that y\oplus z = y+z = \frac{S}{2}, as we want.
That only leaves the case where \frac{S}{2} has only one set bit; meaning it’s a power of 2.
This also means S is itself a power of 2.
In this case, no solution exists!
Proof
Let S = 2^k.
If k = 0 or k = 1, meaning S = 1 or S = 2, clearly no solution can exist; so let’s assume k\geq 2.
Recall that for the XOR to be 0, an even number of elements should have each bit set; which in our case means either 0 or 2 elements can have each bit.
Clearly, bits higher than the k'th can’t be set at all; otherwise the sum would exceed 2^k.
If two elements have the (k-1)'th bit set, their sum is already 2^{k-1} + 2^{k-1} = 2^k.
This means the third element is forced to be 0, which isn’t allowed.
Now we’re left with only bits \leq k-2.
But we have at most 2 of each of them, so the maximum possible sum if 2\cdot (2^0 + 2^1 + \ldots + 2^{k-2}) = 2\cdot (2^{k-1} - 1) = 2^k - 2, meaning it’s not possible to attain a sum of S = 2^k.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Author's code (C++)
// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
void solve()
{
int n,s;
cin >> n >> s;
if(s%2){
cout << "-1\n";return;
}
if(s < n){
cout << "-1\n";return;
}
if((n%2) == 0){
// cout << "YES\n";
cout << (s-n+2)/2 << " " << (s-n+2)/2;
rep(i,2,n){
cout << " " << 1;
}cout << "\n";
return;
}
if(n >= 5){
if(s >= n+3){
// cout << "YES\n";
cout << 1 << " " << 2 << " " << 3;
n -= 3;
s -= 6;
if(n){
cout << " " << (s-n+2)/2 << " " << (s-n+2)/2;
rep(i,2,n){
cout << " " << 1;
}
}
cout << "\n";
return;
}
else{
cout << "-1\n";return;
}
}
if(n == 1){
cout << "-1\n";return;
}
if(n == 3){
if(bpc(s) == 1){
cout << "-1\n";return;
}
// cout << "YES\n";
int a = 0,b = 0;
rep(i,1,30){
if(s & (1<<i)){
a = (1<<(i-1));
b = a;
s ^= (1<<i);
break;
}
}
rep(i,1,30){
if(s & (1<<i)){
s ^= (1<<i);
s ^= (1<<(i-1));
a ^= (1<<(i-1));
}
}
cout << s << " " << a << " " << b << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef NCR
init();
#endif
#ifdef SIEVE
sieve();
#endif
int t;cin >> t;while(t--)
solve();
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--)
{
int n,sum;
cin>>n>>sum;
if(sum%2 or n==1)
{
cout<<-1<<endl;
}
else
{
if(n%2)
{
if(n>3)
{
if(sum-6>=n-3)
{
cout<<1<<" "<<2<<" "<<3<<" ";
cout<<(sum-6-(n-5))/2<<" "<<(sum-6-(n-5))/2<<" ";
for(int i=0;i<n-5;i++)
cout<<1<<" ";
cout<<endl;
}
else
cout<<-1<<endl;
}
else
{
int gg=__builtin_popcount(sum/2);
int p=1;
while(p<(sum/2))
{
p*=2;
}
p/=2;
if(gg>1)
{
cout<<sum/2<<" "<<sum/2-p<<" "<<p<<endl;
}
else
cout<<-1<<endl;
}
}
else
{
if(n>sum)
cout<<-1<<endl;
else
{
cout<<(sum-(n-2))/2<<" "<<(sum-(n-2))/2<<" ";
for(int i=0;i<n-2;i++)
cout<<1<<" ";
cout<<endl;
}
}
}
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n, s = map(int, input().split())
if s < n or s%2 == 1:
print(-1)
continue
if n%2 == 0:
x = (s-n+2) // 2
ans = [x, x] + [1]*(n-2)
print(*ans)
else:
if n > 3:
if s-6 < n-3: print(-1)
else:
x = (s-6-n+5)//2
ans = [1, 2, 3, x, x] + [1]*(n-5)
print(*ans)
elif n == 3:
if s < 6: print(-1)
elif s&(s-1) == 0: print(-1)
else:
s //= 2
for i in range(30):
if s & 2**i:
print(2**i, s - 2**i, s)
break
else: print(-1)