You are not logged in. Please login at www.codechef.com to post your questions!

×

VCS - Editorial

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

This question is marked "community wiki".

asked 19 Apr '15, 20:51

mogers's gravatar image

5★mogers
659716
accept rate: 25%

edited 11 Feb '16, 17:53

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 20 Apr '15, 00:38

harshvk5's gravatar image

3★harshvk5
314
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★

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

answered 21 Sep '15, 10:42

main_beer_hoon's gravatar image

4★main_beer_hoon
362
accept rate: 50%

edited 21 Sep '15, 10:44

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

link

answered 24 Sep '15, 20:32

sanket407's gravatar image

4★sanket407
4849
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.

link

answered 25 Dec '15, 22:32

miteshukate's gravatar image

0★miteshukate
11
accept rate: 0%

edited 25 Dec '15, 22:37

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

}

link

answered 12 Sep '16, 01:32

shivamnema05's gravatar image

0★shivamnema05
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); } }

link

answered 29 Jan '17, 02:16

abhishek_sv's gravatar image

1★abhishek_sv
1
accept rate: 0%

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;

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

link

answered 18 Mar '17, 10:09

jainsaarthak's gravatar image

0★jainsaarthak
1
accept rate: 0%

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

link

answered 12 Dec '17, 02:24

sprea27's gravatar image

2★sprea27
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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