×

# VCS - Editorial

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

Easy.

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:

This question is marked "community wiki".

5★mogers
659716
accept rate: 25%

19.8k350498541

 0 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. answered 20 Apr '15, 00:38 3★harshvk5 3●1●4 accept rate: 0% A boolean array is hashing in this case :) (20 Apr '15, 01:07) mogers5★ ^ That too :) (20 Apr '15, 11:22) harshvk53★
 0 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 int main() { int t,i,n,m,k,j,z; scanf("%d",&t); for (i=0;i
 0 @main_beer_hoon in the last for loop start j from 1 and not 0 as 1<=n<=100 answered 24 Sep '15, 20:32 484●9 accept rate: 10%
#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.

11
accept rate: 0%

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

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


}

1
accept rate: 0%

# 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<int> a,b,c; for(int i=0;i<m;i++) { int p; scanf("%d",&p); a.insert(p); } for(int i=0;i<k;i++) { int p; scanf("%d",&p); a.insert(p); } int l=a.size(); printf("%d %d\n",m+k-l,n-l); } }

1
accept rate: 0%

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

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

1
accept rate: 0%

 0 Can someone please tell me what is wrong with this code? https://www.codechef.com/viewsolution/16556494 answered 12 Dec '17, 02:24 2★sprea27 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,657
×1,649
×160
×62
×5

question asked: 19 Apr '15, 20:51

question was seen: 4,698 times

last updated: 12 Dec '17, 02:24