VCS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Konstantsin Sokol
Tester: Gedi Zheng
Editorialist: Miguel Oliveira

DIFFICULTY:

Easy.

PREREQUISITES:

Sets.

PROBLEM

Given 2 sets of integers, count the number of integers that appear in both sets and the number of integers between 1 and N that do not appear in either set.

QUICK EXPLANATION

The source files that are both tracked and ignored are the intersection of the two sets given in the input.

The source files that are both untracked and unignored are the numbers in the interval [1, N] that do not appear in either of the given lists.

EXPLANATION

We are given 2 lists of unique integers. We can treat these lists as sets. A set is a collection of distinct items (integers in this case).

Both ignored and tracked source files

The source files that are both tracked and ignored are the integers in the intersection of the 2 given sets.

To calculate the set intersection, the simplest way is to search all integers of the first set in the second set. Since we have only 100 numbers, we could do this search naively with 2 nested loops and a time complexity of O(M*K).

A smarter way is to use a hash table. Note that the numbers are between 1 and 100. We can use an array with 100 positions and mark position i if number i is in the set. This way we can look-up if a number is in a set in O(1) time. Thus, the time complexity of the set intersection is O(M) to build set A, O(K) to build set B and O(M) to check if the items in set A appear in set B. The total time complexity of this set intersection is O(M+K).

Also, you can use set, map, unordered_map in C++ to make a look up table too.

Also, sometimes you can use bitwise operations with bit packing the sets in the integer to int or long data type. Then, you can use bitwise operations (e.g. and, or, xor) to check set intersection. Also, for two sorted arrays a, b, you can use set_intersection in C++ to find number of common elements in both the arrays in linear time.

Both unignored and untracked source files

The number of source files that are both untracked and unignored are the integers between 1 and N that do not appear in set A or B. We can use the same logic and search all numbers between 1 and N in sets A and B. This will take O(N) time if we use hashing or O(N * (M+K)) with the naive search.

Time Complexity

The total time complexities are O(N + M + K) using hashing and O(M * K + N * (M+K)). Both were perfectly fine as the size of the sets are up to 100.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution

1 Like
2

Maintaining two boolean arrays also suffices. Make one pass over both arrays, and mark out the points present in them. THen with one pass, check if two corresponding values are 1 or 0 simultaneously, to get the answers for part 1 and 2 respectively.

3

A boolean array is hashing in this case :slight_smile:

4

^ That too :slight_smile:

5

Can anyone tell me what’s wrong with this code? I am always getting wrong answer with this, and am unable to understand why.

#include<stdio.h>
int main()
{
    int t,i,n,m,k,j,z;
    scanf("%d",&t);
    for (i=0;i<t;i++)
    {
        scanf("%d%d%d",&n,&m,&k);
        int ti=0,uu=0;
        int arr[100][2]={10};
        for (j=0;j<m;j++)
        {
            scanf("%d",&z);
            arr[z][0]=1;
        }
        for (j=0;j<k;j++)
        {
            scanf("%d",&z);
            arr[z][1]=1;
        }
        for (j=0;j<=n;j++)
        {
            if (arr[j][0]==1 && arr[j][1]==1)
                ti++;
            if (arr[j][0]==0 && arr[j][1]==0)
                uu++;
        }
        printf("%d %d\n",ti,uu);
    }
    return 0;
}
6

@main_beer_hoon
in the last for loop start j from 1 and not 0 as 1<=n<=100

7

#include<stdio.h>
#define gc getchar_unlocked
int read_int() {
char c = gc();
while(c<‘0’ || c>‘9’) c = gc();
int ret = 0;
while(c>=‘0’ && c<=‘9’) {
ret = 10 * ret + c - 48;
c = gc();
}
return ret;
}
int main(){
int T;
int N,M,K;
int ign[100]={0},track[100]={0};
int temp,i,j;

T = read_int();
while(T–){
N = read_int();
M = read_int();
K = read_int();
int ti=0;
int ntni = 0;
for(i=0;i<M;i++){
temp=read_int();
++ign[temp];
}
for(i=0;i<K;i++){
temp=read_int();
track[temp];
if(ign[temp]){
ti++;
}
}
ntni = N-((M+K)-ti);
printf("%d %d \n",ti,ntni);
}

return (0);
}

Can you guys please tell me whats wrong in my program its giving wrong answer.I checked with sample inputs.

8

Can any one tell me what is wrong with this code. It’s correct with public test cases.
#include
#include
#include
#include

#define pb push_back
//[Version Control System]problem codechef. Date : [11 Sep 2016, 10:31AM].
//Shivamnema05
using namespace std;
int N; //no of source files
int M ; //no of ignored files
int K; //no of tracked files

int main(void) {
int T, i;
cin >>T;
while(T–){

    int scrfile[100] = {0};
    cin >>N >>M >>K;
    int tracked =0 , untracked = 0,val = 0;
    
    for (i=0 ; i<M ; i++ ){
        cin >> val;   
        scrfile[val]++;
    }
            
    for (i =0 ; i<K ; i++ ){
        cin >> val;
        scrfile[val]++;
    }
    for (i=1 ; i<=N ; i++){
        if(scrfile[i] == 2){
            tracked++;
        }else if(scrfile[i] == 0) {
            untracked++;
        }
    }
    cout<<tracked<<" "<<untracked<<endl;
    
}
return 0;

}

9

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
int n,m,k;
scanf("%d %d %d",&n,&m,&k);
set a,b,c;
for(int i=0;i<m;i++)
{
int p;
scanf("%d",&p);
a.insert§;
}
for(int i=0;i<k;i++)
{
int p;
scanf("%d",&p);
a.insert§;
}
int l=a.size();
printf("%d %d\n",m+k-l,n-l);
}
}

10

Can any one tell me what is wrong with this code. It’s correct with public test cases.

#include
#include<math.h>
using namespace std;

int main()
{
int tc,n,m,k,trackedandignored,untrackedandunignored;
cin>>tc;

for(int i=0;i<tc;i++)
{
cin>>n>>m>>k;
int ignored[m],tracked[k];
trackedandignored=0;
untrackedandunignored=0;

for(int j=0;j<m;j++)
cin>>ignored[j];

for(int j=0;j<k;j++)
cin>>tracked[j];

int x=0,y=0;
for(int j=1;j<=n;j++)
{
    if(ignored[x]!=j && tracked[y]!=j)
    untrackedandunignored++;
    
    else if(ignored[x]==j && tracked[y]==j)
    {
        trackedandignored++;
        x++;
        y++;
    }
    
    else if(ignored[x]==j)
    x++;
    
    else if(tracked[y]==j)
    y++;
}

cout<<trackedandignored<<" "<<untrackedandunignored<<endl;

}

return 0;
}

11

Can someone please tell me what is wrong with this code?
https://www.codechef.com/viewsolution/16556494