NOBEL - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Cakewalk

PREREQUISITES:

Implementation

PROBLEM:

You are given two integers N and M denoting the total number of researchers and the total number of fields respectively, You are also given an array A where A_i denotes the field where i^{th} researcher is working.

You need to tell whether Chef can win the prize this year. Chef wins the prize if he works in a unique field.

EXPLANATION:

Since the criteria of winning the Nobel Prize is to work in a unique field. Hence we just need to find if there is a field where no researchers are working.

The naive solution is to check for every field i (1 to M) if for this field there are no researchers that are working on it. If there is a field where no researchers are working then our Chef can work on this field and win the Nobel Prize.

However, the time complexity for the above solution would be too high and hence it will result in Time Limit Exceeded. To optimize it further, we can hash every field where i^{th} researcher is working. Now if there exists any field which is not present in hash then Chef can work on this field and win the Nobel Prize.

TIME COMPLEXITY:

O(N+M)

However, it depends on the way of implementation.

SOLUTIONS:

Setter
#include<bits/stdc++.h>
 
using namespace std;
 
const int minv = 1, maxv = 1e5, maxtn = 1e6, maxt = 1e5;
const string newln = "\n", space = " ";
 
int main()
{   
    int t; cin >> t;
    int totn = 0, totm = 0;
    while(t--){
        int n, m; cin >> n >> m; totn += n; totm += m;
        bool visit[m + 1]; memset(visit, false, sizeof(visit)); 
        for(int i = 1; i <= n; i++){
            int x; cin >> x;
            visit[x] = true;
        }
        bool ans = false;
        for(int i = 1; i <= m; i++){
            if(!visit[i]){
                ans = true; break;
            }
        }
        string p = ans ? "Yes" : "No";
        cout << p << endl;
    }
    assert(totn <= maxtn);
    assert(totm <= maxtn);
} 
Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef double f80;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ll,ll> pll;
#define double long double
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b>0) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int sum_n=0,sum_m=0;
void solve() {
	int n=readIntSp(1,100000),m=readIntLn(1,100000);
	sum_n+=n;
	sum_m+=m;
	assert(sum_n<=1000000&&sum_m<=1000000);
	set<int> tem;
	fr(i,1,n) {
		int te;
		if(i!=n)
			te=readIntSp(1,m);
		else
			te=readIntLn(1,m);
		tem.insert(te);
	}
	string ans;
	if(sz(tem)<m) {
		ans="yes";
	} else {
		ans="no";
	}
	for(char &i:ans) {
		if(rng(2))
			i=i-'a'+'A';
	}
	cout<<ans<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(1);
	int t=readIntLn(1,100000);
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
 
Editorialist
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve()
{
  int n,m;
  cin>>n>>m;
 
  set <int> s1;
 
  for(int i=0;i<n;i++)
  {
    int x;
    cin>>x;
 
    s1.insert(x);
  }
 
  if(s1.size()==m)
    cout<<"NO"<<"\n";
  else
    cout<<"YES"<<"\n";
}
 
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
 
  int t;
  cin>>t;
 
  while(t--)
    solve();
 
return 0;
}
 
2 Likes

https://www.codechef.com/viewsolution/44266199

Why TLE in this code?

3 Likes

hey, I used this same approach used by Editorialist but I was still getting T.L.E, please have a look at my code:
https://www.codechef.com/viewsolution/44273405

1 Like

because u have to implement hash tree otherwise the time complexity goes first o(n) for setting values and nlog(m) for searching each element in the array and according to editorial you must have to implement the code in log(n+m) time complexity hope you understand <3 <3 :kissing_heart:

#include <map>
#define ll long long
using namespace std;
void solve()
{
    ll n,m;
    // ll a[100000];
    cin>>n>>m;
    set<int,greater<int>> s1;
    for(int i = 0;i<n;i++)
    {
        int e;
        cin>>e;
        s1.insert(e);
    }
    ll cnt = 0;
set<int, greater<int> >::iterator itr;
        for (itr = s1.begin(); itr != s1.end(); itr++)
    {
        cnt++;
    }
    // cout<<endl;
    // for(int i = 0;i<n;i++)
    // {
    //   cout<<s1[i]<<endl;
    // }
    if(cnt<m) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
int main() {
	ll t;
	cin>>t;
	while(t--)
	{
	  solve();
	}
	return 0;
}

why getting tle?

please have a look at the Editorialist’s code, I think my code is pretty similar

1 Like
#include <map>
#define ll long long
using namespace std;
void solve()
{
    ll n,m;
    ll a[100000];
    cin>>n>>m;
    for(int i = 0;i<n;i++) cin>>a[i];
    ll f[100000]={0};
    ll cnt = 0;
    for(int i = 0;i<n;i++)
    {
        f[a[i]]++;
    }
    // for(int i = 0;i<10;i++) cout<<f[i]<<" ";
    // cout<<endl;
    for(int i = 0;i<m;i++)
    {
        if(f[i]>0) cnt++;
    }
    // cout<<cnt<<endl;
    if(cnt<m) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
int main() {
	ll t;
	cin>>t;
	while(t--)
	{
	  solve();
	}
	return 0;
}

this is my second code but still tle.

If I would have replaced n to m It could have passed all the test, My Bad :frowning:

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

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
long long n,m;
cin>>n>>m;
long long a[n],b[n]={ 0 };
int i;
int count=0;
if(m>n)
{
cout<<“YES”<<endl;
}
else
{

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

}
can anyone tell me why i was getting run time error in this solution?it is passing all the test cases.

Can we divide the question into two parts?
Case 1 - When m>n. In this case shouldn’t the answer always be YES?
Case 2 - When m<=n. Here we can use the solution given in the editorial.
I tried doing this but I am getting WA. Is the above approach correct?

If the input has large no. of integers in single line, better to use “.readLine” and parse to extract the integers.

See, 2 Java AC solutions on this problem:
https://www.codechef.com/viewsolution/44286167
https://www.codechef.com/viewsolution/44286878

I’m following the approach given below but getting WA. Please help.

  • Create an array of size m
  • Memset this array with 0
  • Now, for each input increment the position of the array with index input-1
  • Sort this array
  • If the first position of this array is 0 then print YES else NO

My code

create array of size m+1
and to solve tle error use fast input output.
if you are using java can store all the answers in stringbuilder with space then print it at once after last test case.

//For c++
Those whoevere are facing TLE error use “\n” for new line instead of endl;
and use ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

OK, thanks

in editorialist code why is it s1.size()==m
why it is nots1.size()>=m

The obvious problem with splitting off the test for N < M is that you have a line of uninteresting input that you must read past. I think that’s your issue. My Python solution made exactly this test, and included an extra read in that branch, so no errors.

T = int(input())
for ti in range(T):
    N,M = map(int,input().split())
    if N < M:
        print("Yes")
        input()
    else:
        if len(set(map(int,input().split()))) < M:
            print("Yes")
        else:
            print("No")

Hello there I have submitted code and I tried various of them even the editorial solution, refrencing another solution which was similar but I am still having wrong answer, please can my code be checked because I am unable to find what I am doing wrong. Here’s my code
https://www.codechef.com/viewsolution/69912363