PROBLEM LINK:
Author: Hritik Aggarwal
Tester: Yash Chandnani
Editorialist: Michael Nematollahi
DIFFICULTY:
SIMPLE
PREREQUISITES:
XOR
PROBLEM:
You are given a N non-negative integers in their binary representations. As long as there are at least two numbers in this set, you take two of them and replace them with their xor.
If you choose the order of the operations optimally, what is the maximum number of bits in the final number that you can achieve?
QUICK EXPLANATION:
The order of operations does not matter. Hence, you can do the operations in an arbitrary order and find out what the final result is.
EXPLANATION:
The first thing to notice is that when two contestants A and B fight, it doesn’t matter who wins. The winner ends up with the same set of weapons regardless of whether it’s A or B.
The next thing to note is that if we think of the input strings as binary representations of integers,
when two contestants with sets of weapons S and T fight, the winner’s set of weapons will be S \oplus T.
The above-mentioned two observations convert the original problem statement to the shorter version described above in the PROBLEM section.
Finally, because the XOR operations is both commutative and associative, it doesn’t matter in which order we arrange the fights; the final resulting number will always be the same.
Another way to think about this is that the final contestant will have the i^{th} weapon iff there are an odd number of contestants who have the i^{th} weapon at the beginning. The reason is that the outcome of a battle does not change the parity of the number of contestants who have the i^{th} weapon (you can confirm this by drawing all possible scenarios).
What this means is that we can arrange the fights in any arbitrary order and check what the final number is and output the number of bits in it set to 1.
The overall time complexity of this solution is O(N).
To view an implementation of the described solution, refer to the editorialist’s solution.
SOLUTIONS:
Setter's Solution
/******************************************
* AUTHOR : HRITIK AGGARWAL *
******************************************/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
#define MOD 1000000007
#define dd double
#define vi vector<int>
#define vll vector<ll>
#define forr(i, n) for(int i = 0; i < n; i++)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep1(i,b) for(int i=1;i<=b;i++)
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define ms(s, n) memset(s, n, sizeof(s))
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define int ll
ll po(ll a, ll x,ll m){ if(x==0){return 1;}ll ans=1;ll k=1; while(k<=x) {if(x&k){ans=((ans*a)%m);} k<<=1; a*=a; a%=m; }return ans; }
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("b.txt", "w", stdout);
#endif
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s[n];
forr(i,n){
//cout<<"a";
cin>>s[i];
}
//cout<<s[0]<<"\n";
if(s[0].length()==1){
int ans=0;
for(int i=0;i<1;i++){
int sum=0;
forr(j,n){
int nu = s[j][i]-'0';
sum^=nu;
}
ans+=sum;
}
cout<<ans<<"\n";
}
else{
int ans=0;
for(int i=0;i<10;i++){
int sum=0;
forr(j,n){
int nu = s[j][i]-'0';
sum^=nu;
}
ans+=sum;
}
cout<<ans<<"\n";
}
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
char ch=getchar();
int v=0;
int sgn=1;
if(ch=='-')sgn=-1;
else{
assert('0'<=ch&&ch<='9');
v=ch-'0';
}
while(true){
ch=getchar();
if('0'<=ch && ch<='9')v=v*10+ch-'0';
else{
assert(ch==nxt);
break;
}
}
return v*sgn;
}
string rword(char nxt){
string ans="";
while(true){
char ch=getchar();
if(ch==nxt)break;
ans.push_back(ch);
}
return ans;
}
int main(){
int t=rint('\n');
while(t--){
int n=rint('\n');
assert(1<=n&&n<=1e5);
vector<int>ans(123,0);
vector<string>all;
for(int i=0;i<n;i++){
string b=rword('\n');
for(char ch:b)assert(ch=='0' || ch=='1');
all.push_back(b);
for(int j=0;j<int(b.size());j++){
ans[j]^=(b[j]-'0');
}
}
for(int i=1;i<n;i++)assert(all[i].size()==all[i-1].size());
int o=0;
for(int x:ans)o+=x;
printf("%d\n",o);
}
assert(getchar()==EOF);
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
int n; cin >> n;
int x = 0;
while (n--){
string s; cin >> s;
reverse(s.begin(), s.end());
int y = 0;
for (int j = 0; j < 10; j++)
if (s[j] == '1')
y ^= 1<<j;
x ^= y;
}
cout << __builtin_popcount(x) << "\n";
}
return 0;
}
