PROBLEM LINK:Author: Konstantsin Sokol DIFFICULTY:Easy. PREREQUISITES:Sets. PROBLEMGiven 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 EXPLANATIONThe 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. EXPLANATIONWe 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 lookup 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".
asked 19 Apr '15, 20:51

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

Can anyone tell me what's wrong with this code? I am always getting wrong answer with this, and am unable to understand why.
answered 21 Sep '15, 10:42

@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

define gc getchar_unlockedint 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. answered 25 Dec '15, 22:32

Can any one tell me what is wrong with this code. It's correct with public test cases. #include <iostream> include <list>include <vector>include <algorithm>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;
} answered 12 Sep '16, 01:32

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+kl,nl); } } answered 29 Jan '17, 02:16

Can any one tell me what is wrong with this code. It's correct with public test cases. include<iostream>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;
} return 0; } answered 18 Mar '17, 10:09

Can someone please tell me what is wrong with this code? answered 12 Dec '17, 02:24
