IMDB - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: Daanish Mahajan
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given the IMDB rating (R_i) and space taken (S_i) of N movies, and the amount of free space X on Chef’s hard disk, find the highest rated movie which can fit on Chef’s disk.

EXPLANATION:

It is enough to simply implement exactly what the problem asks for.
The constraints guarantee that X\geq min (S_i), so at least one movie will fit on the disk.
Initialize an answer variable, ans = 0.
Iterate over all the N movies. For each i, if the S_i\leq X, set ans = max(ans, R_i)
At the end, ans is the required answer.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

SOLUTIONS:

Setter's Solution (C++) 
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
 
using namespace std;
 
const int maxn = 1e5, maxt = 10, minv = 1, maxv = 1e9;
 
int main()
{   
    int t; cin >> t;
    while(t--){
        int n, space; cin >> n >> space;
        int ans = 0;
        for(int i = 0; i < n; i++){
            int s, r; cin >> s >> r;
            if(s <= space)ans = max(ans, r);
        }
        assert(ans > 0);
        cout << ans << endl;
    }
Tester's Solution (C++) 
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
 
int main(){
    fastio;
 
    int t;
    cin>>t;
    while(t--){
        long long int n, x, s, r;
        cin>>n>>x;
        long long int ans = -1e9;
        for(int i = 0; i < n; i++){
            cin>>s>>r;
            if(s <= x) ans = max(ans, r);
        }
        cout<<ans<<endl;
    }
 
    return 0;
}
Editorialist's Solution (Python) 
t = int(input())
for _ in range(t):
    n, x = map(int, input().split())
    best = 0
    for i in range(n):
        space, rating = map(int, input().split())
        if space <= x:
            best = max(best, rating)
    print(best)
2

//What’s wrong in this code

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
long n,a,b,i,maxi,x;

cin>>t;
while(t--)
{
    maxi=INT_MIN;
    cin>>n>>x;
    unordered_map<long,long> m;
    for(i=0;i<n;i++)
    {
        cin>>a>>b;
        m.insert({a,b});
    }
    for(auto it=m.begin();it!=m.end();it++)
    {
        if(it->first<=x)
        {
            maxi=max(maxi,it->second);
        }
    }
    cout<<maxi<<endl;
}

}

3

Easy af, my solution :-

for _ in range(int(input())): # 3
    n,x=map(int,input().split()) # 3 2
    ans=0
    for __ in range(n): # 3 
        s,r=map(int,input().split()) # 1 51
        if s<=x and r>ans: # 1<=2 and 51>0
            ans=r # replace if condition is valid
    print(ans)