PALINT - Editorial

sriharika05 · September 16, 2021, 9:44am

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

joffan · September 16, 2021, 12:58pm

@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.

tushar009 · September 16, 2021, 3:07pm

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]CodeChef: Practical coding for everyone

Thanks in Advance

joffan · September 16, 2021, 3:23pm

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

1
1 0
1

jawa2code · September 16, 2021, 4:26pm

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

please fail this

jawa2code · September 17, 2021, 2:08pm

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

please fail this

imnirajky2001 · September 18, 2021, 9:40am

#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???

jawa2code · September 19, 2021, 3:03pm

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

jawa2code · September 20, 2021, 8:45am

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 · September 21, 2021, 4:02am

joffan · September 22, 2021, 8:08am

@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()

jawa2code · September 22, 2021, 9:24am

Thanks a lot @ joffan
please see java impl at CodeChef: Practical coding for everyone
let me know failed test case

joffan · September 22, 2021, 1:28pm

@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.

jawa2code · September 22, 2021, 1:31pm

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

joffan · September 22, 2021, 1:50pm

@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.

jawa2code · September 22, 2021, 2:36pm

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

jawa2code · September 23, 2021, 10:10am

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

solved

chandra8226 · September 23, 2021, 8:51pm

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

messi_code · September 24, 2021, 9:41am

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

Store all values in map (along with frequencies) & call it MP1. Also keep count of max freq element in original values.
Traverse MP1 and check if new map (MP2) has xor of this num available.
If not then push this num normally in MP2 along with its freq.
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).
Repeat from step 2 for whole MP1.
If x==0 or max count of freq in orig is >= curr freq then ans is origFreq & 0.
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";
  }
}

joffan · September 24, 2021, 10:22am

@messi_code try the following input:

1
8 2
1 3 5 5 7 7 7 7