Wa in version control system

1

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

2

anyone help me where i’m wrong

3

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

4

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

5

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.

6

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
7

Thank you @akshitm16

1 Like
8

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