PALINT - Editorial

can someone kindly tell me what is wrong with my code since it is showing wrong answer. Thanks in advance!


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

int main() {
    ll no_of_testcases;
    ll n,x;
    cin>>no_of_testcases;
    
    for(ll i=0;i<no_of_testcases;i++)
    {
        map <ll,ll> mp;
        
        
        
        cin>>n;
        cin>>x;
        ll first=0;
        ll input,second,answer,second_doop;
        set<ll> st;
        //cout<<first<<endl;
        for(int j=0;j<n;j++)
        {
           cin>>input;
            mp[input]=mp[input]+1;
            st.insert(input);
            
        }
        ll val;
        for(auto it=st.begin();it!=st.end();it++)
        {
            answer=mp[*it];
            
            if(x!=0)
            {
            answer=answer+mp[(*it)^x];
            }
            
            if(answer>first)
            {
                first=answer;
                second=mp[(*it)^x];
            }
            else if(answer==first)
            {
                
               
                second=min(second,mp[(*it)^x]);
            }
           
            
            
        }
        cout<<first<<" "<<second<<endl;
    }
	// your code goes here
	return 0;
}

@odalock One issue, anyway; you use break from the X==0 case - you should use continue as there may be subsequent cases.

Another suggestion (this is not a bug) is to use the Counter structure where you’re hand-counting in the defaultdict at the moment. A Counter will return a zero count for missing elements without any check.

1 Like

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 tushar009 [50934241]Solution: 50934241 | CodeChef

Thanks in Advance

@tushar009 Try this almost-too-simple test case:

1
1 0
1

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

please fail this

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

please fail this

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define mod 1000000007

void testCase(){
ll n, k;
cin>>n>>k;
int count = 0, ops = 0;
vector v(n);
unordered_map<int, int> my;

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

    if(my.count(v[i])){
        my[v[i]]++;
    }else{
        my[v[i]] = 1;
    }

    count = max(count, my[v[i]]); 
}


for(int i=0; i<n; i++){
    int ans = (v[i]^k);
    if(my.count(ans)){
    if(count <= (my[ans] + my[v[i]])){
        count = (my[ans] + my[v[i]]);
        if(ops > my[v[i]]){
        ops = my[v[i]];
        }
    }
    }
}

cout<<count<<" "<<ops<<endl;

}

int main(){
ll t = 1;
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>t;
while(t–){
testCase();
}
}

why I am getting WA???

Is it really required to handle x==0,not possible to generalize?

Hello joffan,
https://www.codechef.com/viewsolution/51005034
this is my approach:
1)read a number
2)find it is present in the actualCntMap,
if it is there then increase the counter
get the maxCount
go to step-1
3)if number is not in the actualCntMap
get the xor of number
if xor not in the actualCntMap
this number is first time appeard
enter the number(not xor) in to actualCntMap and set 1
if xor present in actualCntMap
increase the count in actualCntMap and opsCntMap
get the maxCount
go to step-1

once reading all numbers done
process the maps to get the minimum operations cpount

iterate all the key’s and values from actualCntMap
if value==maxCount
get the opsCnt from opsCntMap
set the minumOpsCnt with the help of result and opsCnt
if the opsCnt <(result-opsCnt)
get the minmum from op_cnt
else
get the minumum from (result - op_counter.get(key))

After iterating all the map we will get maximum result and minimum opsCnt

@jawa2code I implemented your algorithm in Python, AC no issue. Could it be a data type problem?

def main():
    T = int(input())
    a_cnt = dict()
    op_cnt = dict()
    while T > 0:
        T -= 1
        N,X = map(int,input().split())
        a_cnt.clear()
        op_cnt.clear()
        result = 1
        for a in map(int,input().split()):
            if a in a_cnt:
                a_cnt[a] += 1
                if a_cnt[a] > result:
                    result = a_cnt[a]
            else:
                xora = a^X
                if xora not in a_cnt:
                    a_cnt[a] = 1
                else:
                    a_cnt[xora] += 1
                    if xora in op_cnt:
                        op_cnt[xora] += 1
                    else:
                        op_cnt[xora] = 1
                    if a_cnt[xora] > result:
                        result = a_cnt[xora]

        minop = N
        for val, cnt in a_cnt.items():
            if cnt == result:
                if val not in op_cnt:
                    minop = 0
                    break
                op = op_cnt[val]
                if op > cnt - op:
                    op = cnt - op
                if op < minop:
                    minop = op

        print(f'{result} {minop}')

# --------------- #    

main()

Thanks a lot @ joffan
please see java impl at Solution: 51005034 | CodeChef
let me know failed test case

@jawa2code I have no way to know exactly what the failed test case is, plus I don’t really know Java that well. I was only checking your algorithm.

One thing I did slightly differently to your implementation was I didn’t retain the input values in an array, since there is no benefit to doing so.

Hello Joffan,in java implementation i am doing the same
thanks for you help Joffan
WA means,no memory and runtime exceptions ,just wrong code
Regards
Samuel

@jawa2code No; I can pretty clearly see that you retain input values in an array:

			Long a[] = null;
:
				a = new Long[n];
:
 					a[i] = rs.nextLong();

etc… I’m just letting you know that my Python version doesn’t do that, plus I have to handle the “value not present” cases differently of course.

And yes, I know what WA means.

x=6
x=8
it just replace the previous value
in java that will not create any problem,once varible refer another object ,previous will be no longer effect the execution

https://www.codechef.com/submit/complete/51477111

solved

Can Someone please explain why it is giving wrong answer when i’m using unordered_map instead of map in c++??

Hey Joffan,

If you dont mind please help me understand what might be the issue in this algo. Its giving WA but working for all TC i can imagine

  1. Store all values in map (along with frequencies) & call it MP1. Also keep count of max freq element in original values.
  2. Traverse MP1 and check if new map (MP2) has xor of this num available.
  3. If not then push this num normally in MP2 along with its freq.
  4. If XOR available then add both nums freq to prev value(ie freq of prev num pushed in MP2 and curr num).
    Let prev and cur nums be a and b. Then here I check if conversion should be a->b or b->a (whichever is min).
  5. Repeat from step 2 for whole MP1.
  6. If x==0 or max count of freq in orig is >= curr freq then ans is origFreq & 0.
  7. Else ans is max freq and min conversion.

C++ code FYR:

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


int main() {
  int t;cin>>t;
  while(t--)
  {
       map<ll,ll> mp,ch;
       ll n,x,omx=0,y;
       cin>>n>>x;
       for(int i=0;i<n;i++)
       {
            cin>>y;
            if(mp.find(y)!=mp.end())mp[y]++;
            else mp[y]=1;
            omx=max(mp[y],omx);
       }
       ll mxv=0,mxc=10000000000;
       for(auto i:mp)
       {
           ll a=x^i.first;
           if(ch.find(a)==ch.end())
           {
               ch[i.first]=i.second;
           }
           else 
           {
               ch[a]+=i.second;
               if(mxv<=ch[a])
               {
                    mxc=min({mxc,i.second,mp[a]});
                    mxv=ch[a];
               }
           }
       }
      if(omx>=mxv||x==0)
        cout<<omx<<" 0\n";
       else
        cout<<mxv<<" "<<mxc<<"\n";
  }
}

@messi_code try the following input:

1
8 2
1 3 5 5 7 7 7 7