PALINT - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Soumyadeep Pal
Tester: Istvan Nagy
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Bitwise Operators, Observations

PROBLEM:

You are given an array A consisting of N integers and an integer X. Your goal is to have as many equal integers as possible in the array. To achieve this goal, you can do the following operation:

  • Choose an index i (1 \leq i \leq N) and set A_i = A_i \oplus X, where \oplus denotes the bitwise xor operation.

Find the maximum number of equal integers you can have in the final array and the minimum number of operations to obtain these many equal integers.

EXPLANATION:

Let’s divide our problem into two cases when X = 0 and the other when X>0.

Case 1: When X=0

This case is so simple as we know that the xor of any number with 0 is the number itself. That is:

A_i \oplus 0 = X=A_i

Hence it is unnecessary to do perform the xor operation as the resultant is going to remain the same. Therefore, in this case, our answer for the maximum number of equal integers in the final array is equal to the maximum number of given integers in the given array, and the minimum number of operations will be 0.

Case 2: When X>0

In this case, we can either change A_i to A_i \oplus X using one operation, else let it remain as A_i without using any operation.

We can store the count of every element that we can achieve in our final array and the number of operations required to achieve that count. We do it like this for any element A_i of the given array:

  • When we don’t perform any operation in element A_i, then
count[A_i]++;
  • When we perform the xor operation in element A_i, then:
count[A_i \oplus X]++; \\ operations[A_i \oplus X]++

Finally, we can find the element which is the present maximum number of times and the number of operations required to achieve this count. If there are more than one elements whose count is maximum, then we pick that element that requires fewer operations to achieve this count.

Finally, we output the maximum count and the minimum operations.

TIME COMPLEXITY:

O(N) per test case.

SOLUTIONS:

Author
#include<bits/stdc++.h>
using namespace std;
clock_t start = clock();

void solve() {
  int n, x; cin >> n >> x;
  map<int, int> cnt, op;
  for (int i = 0; i < n; i++) {
    int y; cin >> y;
    cnt[y]++;
    if (x != 0) {
      cnt[y ^ x]++;
      op[y ^ x]++;
    }
  }
  int equal = 0, operation = 0;
  for (auto u : cnt) {
    if (u.second > equal) {
      equal = u.second;
      operation = op[u.first];
    } else if (u.second == equal) {
      operation = min(op[u.first], operation);
    }
  }
  cout << equal << ' ' << operation << '\n';
}

signed main() {
  ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) solve();
  cerr << fixed << setprecision(10);
  cerr << "Time taken = " << (clock() - start) / ((double)CLOCKS_PER_SEC) << " s\n";
  return 0;
}


Tester
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
	#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

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) {
			assert(cnt > 0);
			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, ' ');
}

int main(int argc, char** argv) 
{
#ifdef HOME
	if(IsDebuggerPresent())
	{
		freopen("../PALINT-1.in", "rb", stdin);
		freopen("../out.txt", "wb", stdout);
	}
#endif
	int T = readIntLn(1, 10'000);
	int sumN = 0;
	forn(tc, T)
	{
		int N = readIntSp(1, 100'000);
		sumN += N;
		int X = readIntLn(0, 1'000'000'000);
		vector<int> A(N);
		map<int, int> m1, m2;
		int bestA1 = 0, bestA2 = 0;
		forn(i, N)
		{
			if(i + 1 == N)
				A[i] = readIntLn(0, 2'000'000'000);
			else
				A[i] = readIntSp(0, 2'000'000'000);
			m1[A[i]]++;
			m2[min<int>(A[i], A[i] ^ X)]++;
		}
		for (const auto& mv : m2)
		{
			if (mv.second > bestA1)
			{
				bestA1 = mv.second;
				bestA2 = bestA1 - max<int>(m1[mv.first], m1[mv.first ^ X]);
			}
			else if (mv.second == bestA1)
			{
				int tmp = bestA1 - max<int>(m1[mv.first], m1[mv.first ^ X]);
				bestA2 = min<int>(bestA2, tmp);
			}
		}
		printf("%d %d\n", bestA1, bestA2);
	}
	assert(sumN < 500'000);
	assert(getchar() == -1);
	return 0;
}

Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

void solve()
{
	int n,x;
	cin>>n>>x;

	int a[n];
	map <int,int> m1,m2;

	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		m1[a[i]]++;

		if((a[i]^x) != a[i])
		{
			int y = a[i]^x;
			m1[y]++;
			m2[y]++;
		}
	}

	int co = -1;
	int ans = -1;
	int op = 0;

	for(auto itr: m1)
	{
		if(itr.second>co)
		{
			op = m2[itr.first];
			co = itr.second;

		}
		else if(itr.second == co && m2[itr.first]<op)
			op = m2[itr.first];
	}

	cout<<co<<" "<<op<<endl;
}

int32_t main()
{
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

	int t;
	cin>>t;

	while(t--)
		solve();

return 0;
}
3 Likes

Codechef September long
Exor problem (PALINT)

Getting wrong answer can anyone spot that monkey case where its failing?
(i have considered X= 0 exceptions)

#include
#include
#include
#define ll long long
using namespace std;

int main()
{
ll int N;
ll int X,max,a;
int T;
cin>>T;

while(T--)
{   
    map<ll int,ll int>m;
    map<ll int,ll int>m2;
    cin>>N>>X;
    ll int list2[N];
    
    //taking main count
    for(ll int i=0;i<N;i++)
    {
        cin>>a;
        list2[i]=a^X;
        m[a]++;
        m[list2[i]]++;
    }
    
    
    
    //taking only second list count
    for(ll int i=0;i<N;i++)
    {
        m2[list2[i]]++;
    }
    
    
    
    //finding max frequency
    ll int max=m.begin()->second;
    ll int best=m.begin()->first;
    for(auto  x:m)
    {
        if(x.second>max)
        {
            max=x.second;
            best=x.first;
            
        }
        
    }
    if(X==0)
    cout<<max/2<<" ";
    else
    cout<<max<<" ";
    
   
    
    //shortlisting and finding best
    for(auto x:m)
    {
        if(x.second==max)//shortlisting those numbers with max frequency
        {
            if(m2[x.first]<m2[best])//finding best(case where lesser operations required)
            best=x.first;
        }
    }
    if(X==0)
    cout<<0;
    else
    cout<<m2[best]<<endl;
    
}


return 0;

}

My solution is passing all the test cases for which I tried but giving WA on submission.
Anyone please provide me a case for which it is failing.
Link to solution Solution: 51023858 | CodeChef
Thanks in Advance

Solution: 50914273 | CodeChef
Why my solution is giving wrong answer ?

https://www.codechef.com/viewsolution/51025500
My solution ended up as WA as well. Would there be any way in which we can see for ourselves which edge cases are failing? If not, would anyone kindly help us figure out which edge case I missed ?

UPDATE: It seems I didnt compare for lesser number of operations among two sets of xor-able number pairs. My bad. Great problem! :slight_smile:

Video editorial solution code is giving WA on submitting.


void solve(){
  int n;cin>>n;
  int X;
  cin >> X;
  unordered_map<int, int> umap;
  int mx_val = 0;
  for(int i=0; i<n; ++i){
    int x;
    cin >> x;
    umap[x]++;
    mx_val = max(mx_val, umap[x]);
  }

  int mx_ops = 0;

  for(auto [key, val]: umap){
    int xor_val = key ^ X;
    int xor_val_cnt = umap[xor_val];

    int val_new_cnt = val;
    if(X != 0) val_new_cnt += xor_val_cnt;

    if(val_new_cnt > mx_val){
      mx_val = val_new_cnt;
      mx_ops = xor_val_cnt;
    }
    else if(val_new_cnt == mx_val){
      mx_ops = min(mx_ops, xor_val_cnt);
    }
  }
  cout << mx_val << ' ' << mx_ops << "\n";
}

Kindly review my code and suggest changes.

divide code in 2 parts when x==0 and when x>0 also dry run your code

Hello please let me know which test case it is failing
https://www.codechef.com/viewsolution/51005034

I compared but still WA
X==0 special case is not required

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n, x, temp,ans=INT_MIN,count=INT_MAX;
        cin >> n >> x;
        map<ll,ll> mp;
        map<ll,ll> mp2;
        vector <ll> vec;
        for (ll i = 0; i < n; i++)
        {
            cin >> temp;
            vec.push_back(temp);
            if (mp.find(temp) == mp.end())
            {
                mp.insert({temp, 1});
                mp2.insert({temp,0});
            }
            else
            {
                mp.find(temp)->second++;
            }
        }
        if(x==0)
        {
            for(auto &ele:mp)
            {
                if(ans<=ele.second)
                    ans=ele.second;
            }
            cout<<ans<<" "<<0<<endl;
            continue;
        }
        for(auto & ele:vec)
        {
            if (mp.find(ele^x) != mp.end())
            {
                mp.find(ele^x)->second++;
                mp2.find(ele^x)->second++;
            }
        }
        for(auto &ele:mp)
        {
            if(ele.second>=ans&&mp2.find(ele.first)->second<count)
            {
                ans=ele.second;
                count=mp2.find(ele.first)->second;
            }
        }
        cout<<ans<<" "<<count<<endl;
    }
}

can someone verify this code?? And tell me where i went wrong.

https://www.codechef.com/viewsolution/51005034
I did like that

I think if someone is writing an editorial then they should keep it as simple as they can so that anyone can understand the logic. Some use their own templates and stuff which sometimes makes it difficult to understand the code. Editorialist’s & Author’s code is crisp and to the point but Tester’s code is horrible. I mean if you are writing this for a 5 star or 6 star coder then their is no need to write because they probably don’t need it. This time the other two codes were simple but there are times when each code is like that.

Can someone help me in finding the test case for which my program Solution: 51035430 | CodeChef gives the wrong answer? I have handled the x=0 test case in my code.

Solution: 51052957 | CodeChef
Still got WA.

Tester job is to test the problem, he checks the input validations etc. The horrible code you see actually validates the input spaces etc.

two parts not required
https://www.codechef.com/viewsolution/51005034

Not able to figure out the bug, working well in test cases, can someone please help?
https://www.codechef.com/viewsolution/51069315

I got a WA as well, and reviewing other’s solution, I can’t see why mine fails! Can someone please help? Thanks!

Here is my code: Solution: 50801022 | CodeChef

Please Help where this fails.

I tried with Two-sum like approach

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
int t;cin>>t;
while(t–)
{
unordered_map<ll,ll> mp,ch;
ll n,x,omx=0,y;
cin>>n>>x;
for(int i=0;i<n;i++)
{
cin>>y;
mp[y]++; // KEEPING COUNT
omx=max(mp[y],omx); //KEEPING HIGHEST COUNT IN ORIGINAL I/P
}
ll mxv=0,mxc=10000000000;
if(x!=0)
for(auto i:mp)
{
ll a=x^i.first; //CHECKING IF I HAVE XOR IN ORIGINAL ARRAY
if(ch.find(a)==ch.end())
{
ch[i.first]=i.second; // IF NOT THEN SIMPLY UPDATE IN NEW MAP
}
else
{
ch[a]+=i.second;//IF YES THEN UPDATING TOTAL OF CONVERSION COUNT
if(mxv<=ch[a])
{
mxc=min({mxc,i.second,mp[a]});
mxv=ch[a];
}
}
}
if(omx>=mxv)
cout<<omx<<" 0\n";
else
cout<<mxv<<" “<<mxc<<”\n";
}
}

Yes, your point of view is correct. But, if someone had to understand from that then it would have been difficult. Not every editorial has multiple solutions.