SC31 - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

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;
} 

how to solve above code in C

how to solve above code in c

https://www.codechef.com/viewsolution/27880489

P.S. I don’t know how it will benefit you. Still did it to see how different will C be from C++.

yaa i watched your solution by the way i dont know c++

My code is written in C not C++. If you know C, you can move on to C++ in a day. Just need to read an STL cheat sheet.

1 Like

i said i watched your solution because it is written c by the way im just 3 month kid in the world of coding

C++ bitset solution
https://www.codechef.com/viewsolution/27661125

refer here for a simpler c++ solution based on above editorial:
https://www.codechef.com/viewsolution/28495043

1 Like

I have Implemented the Problem in Python:
https://www.codechef.com/viewsolution/29411372

for i in range(int(input())):
arr = []
weapon_sum = 0

for j in range(int(input())):
    arr.append([int(k) for k in input()])

for j in range(10):
    x=0
    for k in range(len(arr)):
        x ^= arr[k][j]
    weapon_sum += x
        
print(weapon_sum)

Hope this might help you!
Suggest if it can be improved.

what is the problem in my code …
#include<stdio.h>
#include<stdlib.h>
int main()
{
int t;
scanf("%d",&t);
if(t>=1 && t<=10)
{
while(t–)
{
int n,i,j,count=0;
scanf("%d",&n);
char str[n+1][11];
for(i=0;i<n;i++)
scanf("%s",&str[i]);
for(i=1;i<n;i++)
{
for(j=0;j<10;j++)
{
str[0][j]=(str[0][j]^str[i][j]);
}
}
for(i=0;str[0][i]!=’\0’;i++)
if(str[0][i]==‘1’)
count++;
printf("%d\n",count);
}
}
return 0;
}
please help to found what problem in this!!!

your code will not work for n=1. So add a condition when n=1.