KJCP02 - Editorial

general
, , , , ,
1

PROBLEM LINK:

Second Year Pains
Practice
Contest

Author: Vatsal Kanakiya
Tester: Dipen Ved
Editorialist: Chaitya Shah

DIFFICULTY:

EASY

PREREQUISITES:

Hashing and STL Maps.

PROBLEM:

Given an array of N integers find out whether the X is in the array or not.

QUICK EXPLANATION:

Take input using A normal array and hash the value using a map to 1.
Now just check if value at X is 1 or not to check if it is in the array or not.

  • Note: In ith iteration X will become
    part of the array and we will have a
    new array of length N+i

EXPLANATION:

Let’s first consider solving the problem for a single test case. We will read N and M first than N integers. Now we want to hash the N integers so we will read each integer using a variable
Let’s say temp and hash it.
So the code looks like:

 for(int i=0;i<N;i++) {
    	        int temp;
    	        scanf("%d",&temp);
    	        M[temp] = 1;
     }

Now we will read M integers and check whether if the value in the map is 1 or not,
If it is 1 we print “YES” (without quotes) and else we print “NO” (without quotes) and hash the value of that integer to 1.
So the code looks like

for(int j = 0;j<M;j++){
	int temp;
	scanf(“%d”,&temp);
	if(M[temp] ) printf(“YES\n”);
	else{
		printf(“NO\n”);
		M[temp] = 1;
    }
}

ALTERNATIVE SOLUTION:

You can also do this using a set and check whether the element is in the set or not.
You can also use a huge array according to the constraints and hash the array without Maps.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

2

can anyone tell me why this is failing?
ll n,m,k;cin>>n>>m;

    rep1(i,1,(n+m)){

        cin>>k;

        if(i<=n)

            mp[k]++;

        else if(i>n){

            if(mp.find(k)!=mp.end()){

                cout<<"YES\n";

            }else{

                cout<<"NO\n";

            }

        }

    }
3

i am not getting whats wrong…the output comes correct still its showing wrong answer

#include
#include<bits/stdc++.h>
#include
#include
#include<unordered_map>
using namespace std;

signed main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
vector a(n+m);
unordered_map<int,int>mp;
for(int i=0;i<(n+m);i++)
{
cin>>a[i];;
mp[a[i]]++;
}

    for(int i=n;i<(n+m);i++)
    {
        if(mp[a[i]]>1)
         cout<<"YES"<<endl;
         else
          cout<<"NO"<<endl;
    }
}
return 0;

}

4

i did the same solution as if the author…in c++ i dont understand how tle is coming

#include
#include<bits/stdc++.h>
#include
#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;

    map<long long ,int>mp;
    long long temp;
    for(int i=0;i<n;i++) {
	        
	        cin>>temp;
	        mp[temp] = 1;
     }
  
    for(int i = 0;i<m;i++){
      cin>>temp;
      if(mp[temp] ) 
        cout<<"YES"<<endl;
     else{
     	cout<<"NO"<<endl;
      	mp[temp] = 1;
       }
  }
}
return 0;

}

5

just because i am using c++ instead of c the program is giving time limit exceed.
i have checked it many times by using cin instead of scanf and cout instead of printf
correct your test cases something is wrong
i have wasted my so much time just to understand where my solution is going wrong…but the problem is not in my solution its in the compiler

1 Like