 # Wa in version control system

https://www.codechef.com/viewsolution/35357027
I don’t know why it is not working.

anyone help me where i’m wrong

Can you explain your logic because I don’t understand what you’ve done?

If you want to solve the problem, you can use hashing.

first i compared two lists and found the similar elements in them.
and then i used a array ‘c’ which has 1 to 100 and and traversed through a and b and made the elements which present in a and b and c as ‘0’ and i found the count of ‘c’ in which the numbers are not equal to 0.

So, basically your fast task is to find common elements in both arrays:
Consider this piece of code-

for(int i=0;i<m;i++)
{
for(int j=i;j<k;j++)
{
if(a[i]==b[j]){
cnt++;
break;
}
}
}


You can check why above fails by using this test case-
array 1 =[1,2,3,4,5]
array2=[6,5,4,3,2,1]
It should be-

for(int i=0;i<m;i++)
{
for(int j=0;j<k;j++)
{
if(a[i]==b[j]){
cnt++;
break;
}
}
}


This is O(M \cdot N) Solution. You can optimize it by hashing in O(N+M+K).

1 Like

Thank you @akshitm16

1 Like

You can take a look at this solution and try to understand-

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

main() {
int t;
cin>>t;
while(t--){
int n,m,k;
cin>>n>>m>>k;
//array of size n; if ith file is ignored then ignored[i]=True else False. Intially we are assuming all files are unignored.
bool ignored[n+1]={0};

//array of size n; if ith file is tracked then tracked[i]=True else False. Intially we are assuming all files are untracked.
bool tracked[n+1]={0};

for(int i=0;i<m;i++){
int var;
cin>>var;
ignored[var]=1;
}

for(int i=0;i<k;i++){
int var;
cin>>var;
tracked[var]=1;
}

int ans1=0;
int ans2=0;
for(int i=1;i<=n;i++){
if(ignored[i] && tracked[i]){ans1++;}
else if(!ignored[i] && !tracked[i]){ans2++;}
}
cout<<ans1<<" "<<ans2<<endl;

}
}


Time Complexity- O(N+M+K).

1 Like