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

1 Like

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.

can anyone tell me what’s wrong with my code?
I am getting wrong answer although test case runs successfully.
//#include<bits\stdc++.h>
#include
#include
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

#define F first
#define S second
#define PB push_back
#define MP make_pair
#define f(i,a,b) for(int i=a;i<b;i++)
#define fr(i,a,b) for(int i=a;i>b;i–)
#define rep(i,n) for(int i=0;i<n;i++)
#define repr(i,n) for(int i=n-1;i>=0;i–)

string compare(string a, string b) {
string x= “”;
for (int i=0; i<10; i++) {
if ((a[i] ==‘1’ && b[i]==‘1’) || (a[i] ==‘0’ && b[i]==‘0’) ){
x += ‘0’;
}
else {
x+= ‘1’;
}
}
return x;
}

int main()
{
/#ifndef ONLINE_JUGJE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
/

/*for string with white spaces
string s;
getline(cin,s);
*/
/*for better io
ios::sync_with_stdio(0);
cin.tie(0);
*/
ll t,n;
cin>>t;
while(t--)
{
	cin>>n;
	string s1;
	cin>>s1;
	string a[n]={s1};
	f(i,1,n)
	{
		cin>>a[i];
	}
	string win=s1;
	f(i,1,n-1)
	{
		win= compare(win,a[i]);
	}
	int c=0;
	f(i,0,10)
	{
		if(win[i]=='1')
		{
			c++;
		}
	}
	cout<<c<<endl;

}


return 0;

}

https://www.codechef.com/viewsolution/40958630
I’ve used naive approach using vectors. Please do share your suggestions :slight_smile:

JAVA SOLUTION @DeepakKumar

/* package codechef; // don’t place package name! */

import java.util.<em>;
import java.lang.</em>;
import [java.io](http://java.io/).*;

/* Name of the class has to be “Main” only if the class is public. <em>/
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
// take Number of test Cases as a Input from the USER
int T = sc.nextInt();
while(T-- > 0){
int n = sc.nextInt();
int result=0;
for(int i=0; i<n; i++){
String str = sc.next();
int len = str.length();
int base = 2;
int power = 0;
int ans=0;
while(len-- > 0){
ans += ((str.charAt(len) - ‘0’ )</em> Math.pow(base, power));
power++;
}
result ^= ans;
}
System.out.println(Integer.bitCount(result));
}

}


}

I have an simple approach using maps.
Observations:
1->It does not matter who wins only 1 weapon of same type will be left at the end.
2->If only 1 weapon left it means that for example if we have 3 weapons of same type then at the end only 1 weapon will be left after all battle ends it can be proved that only weapons which are odd in number will win for example if we have 4 weapon of same type at the end 0 will be left simple.
So, For every string we will just calculate the number of weapon count and store it in a map at the end if(m.second%2!=0) we will update the answer simple.
[Solution Link For better understanding.]
(CodeChef: Practical coding for everyone)