PROBLEM LINK:
Practice
Contest: Division 2
Contest: Division 1
Author: Jannik Kudla
Tester: Rahul Dugar
Editorialist: Aman Dwivedi
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Pigeonhole Principle, Meet in the Middle, Masking
PROBLEM:
You have a pile of N unopened gifts with values A_1,A_2,…,A_N. You wish to distribute some (possibly all) of the gifts among Alice and Bob, and give the rest away to charity. You must do so in such a manner that:
- Alice and Bob get at least one gift each
- each gift is given to at most one of the children, as they do not like to share
- the sum of values of the gifts Alice gets is equal to the sum of values of gifts Bob gets.
You need to distribute the gifts or state that it is impossible to distribute them in a way that satisfies all conditions.
EXPLANATION:
We have an array A of N positive integers. We need to find two non-empty disjoint subsets X, Y ⊆ A with equal sum, i.e. Sum(X) = Sum(Y).
The first observation that we can draw is that the value of N needs not be as large as stated in constraints. Infact there always exists two non-empty disjoint subsets X, Y ⊆ A with equal sum for all values of N \ge 32. Let us try to prove that with the help of Pigeonhole Principle:
Proof
Recall, what the pigeonhole principle says, if there are N holes and N+1 pigeons, then at least one hole will have more than 1 pigeon. As number of pigeons are greater than number of holes. i.e. ((N+1)/N) > 1. Now let’s move towards our question:
The number of subsets we can have for a sequence of length N are 2^N. Also what are the number of distinct values of sum we can find for any subset. The minimum value possible is 1 and the maximum value possible is N*max(A), and it is possible to have all the values from 1 to N*max(A).
Now our subsets will act like pigeons, and the number of distinct sum possible will acts like holes. It is possible to have sum of two subsets equal if:
(2^N / (N*max(A)) \ge 1The maximum value that array A can have is 10^8, according to constraints. So,
(2^N / (N*10^8)) \ge 12^N \ge N*10^8N > 31
Hence for all values of N greater than or equal to 32, we can always find two non-empty disjoint subsets X, Y ⊆ A with equal sum.
Also, we need to care about overlapping of subsets, if any element overlaps in both the sequence, then we will assign that element to charity and the sum still remains same.
In our proof we said that there always exists a sequence, such that it is possible to generate all possible values from 1 to N*max(A). Such sequences are in powers of 2.
From the above fact, we can see that, it is possible to have no two non-empty disjoint subsets X, Y ⊆ A with equal sum for N=27, where sequence can be in the form of {2^0,2^1,.....2^{26}}, since 2^{26} lies well enough inside our constraints.
However for N=28 to N=31, the proof that whether the solution will always exist is beyond the scope of editorialist. So we can try for any N from 28 to 31, hopefully the solution passes for any value of N for this range.
However, the N is still large to not let pass the brute force solution, for this we can use Meet in the Middle approach. Basically. we will divide our sequence into two parts S_1 and S_2 each consisting of N/2 integers and find individually for both of the sequences whether it is possible to find two non-empty disjoint subsets X, Y ⊆ A with equal sum.
The above can be done by using ternary mask, since we have three possibilities to distribute integers, i.e. Alice, Bob and Charity. If in any sequence either S_1 and S_2 we find the possibility of distribution, we are done, else we will try to meet now both the sequences.
Suppose, for sequence S_1, one of the possibility is having sum of A_1 with Alice and B_1 with Bob. Similarly for sequence S_2, one of the possibility is having sum of A_2 with Alice and B_2 with Bob. If in any of the possibility A_1-B_1=A_2-B_2, then it is possible to have the distribution.
We can do so by assigning A_1+B_2 to Alice and A_2+B_1 to Bob. Since A_1+B_2=A_2+B_1. For checking that for every possibility of sequence S_1 with sequence of S_2, we can maintain a hash for that.
If we are unable to find any valid distribution, simply print NO.
TIME COMPLEXITY:
O(3^M) per testcase,
Here M=min(N/2,x), where choosing x depends on you. One such x can be 14.
SOLUTIONS:
Setter
Tester
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(ll a, int b) {
ll res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
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,' ');
}
pii a[100005];
const int num=32;
int lolol;
int allpos1[43046721],allpos2[43046721];
void gogo(int from, int to, int allpos[]) {
lolol=1;
for(int i=from; i<=to; i++) {
for(int j=0; j<lolol; j++) {
allpos[j+lolol]=allpos[j]+a[i].fi;
allpos[j+2*lolol]=allpos[j]-a[i].fi;
}
lolol*=3;
}
}
vector<bool> btset;
char ans[100005];
void solve() {
int n=readIntLn(2,100000);
fr(i,1,n) {
ans[i]='N';
if(i!=n)
a[i].fi=readIntSp(1,100'000'000);
else
a[i].fi=readIntLn(1,100'000'000);
a[i].se=i;
}
int pp=min(num,n);
gogo(1,pp/2,allpos1);
int pc1=lolol;
gogo(pp/2+1,pp,allpos2);
int pc2=lolol;
btset.assign(1'600'000'001,0);
for(int i=1; i<pc1; i++) {
if(allpos1[i]>=0)
btset[allpos1[i]]=1;
if(allpos1[i]==0) {
int index=i;
for(int i=1; i<=pp; i++) {
if(index%3==1)
ans[a[i].se]='A';
else if(index%3==2)
ans[a[i].se]='B';
index/=3;
}
cout<<"YES"<<endl;
fr(i,1,n)
cout<<ans[i];
cout<<endl;
return;
}
}
btset[0]=1;
for(int i=1; i<pc2; i++) {
if(allpos2[i]<=0&&btset[-allpos2[i]]) {
int index=i*pc1;
bool none=1;
for(int j=0; j<pc1; j++) {
if(allpos1[j]+allpos2[i]==0) {
none=0;
index+=j;
break;
}
}
assert(none==0);
for(int i=1; i<=pp; i++) {
if(index%3==1)
ans[a[i].se]='A';
else if(index%3==2)
ans[a[i].se]='B';
index/=3;
}
cout<<"YES"<<endl;
fr(i,1,n)
cout<<ans[i];
cout<<endl;
return;
}
}
cout<<"NO"<<endl;
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(10);
int t=readIntLn(1,5);
// int t=1;
// cin>>t;
fr(i,1,t)
solve();
// assert(getchar()==EOF);
#ifdef rd
cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}