CUTOFF - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: notsoloud
Testers: tabr, yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

N students took a test, the i-th of them scored A_i marks. All the A_i are distinct.
It is known that exactly X children passed the test.
A student is said to have passed if their score is strictly more than the passing mark.

Find the highest possible passing mark.

EXPLANATION:

The constraints are small, so it is possible to simply brute force the answer.

Clearly, the pass mark is between 0 and 100.
Simply try each one, and then iterate across the entire array to count the number of children who passed if this were to be the pass mark.

Among them, print the maximum value such that exactly X students passed.

This has a complexity of \mathcal{O}(100\cdot N), which is good enough.
It is possible (but unnecessary) to solve the problem with a better complexity.

TIME COMPLEXITY

Between \mathcal{O}(N) and \mathcal{O}(100\cdot N) per test case, depending on implementation.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(101):
        passed = 0
        for y in a: passed += y > i
        if passed >= x: ans = i
    print(ans)
2 
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t;
	 cin >> t; 
	 while (t--){
	     
        int n , x; 
        cin >> n >> x;
        int arr[n];
        for ( int i =0 ;i <n;i++) cin >> arr[i];
        sort ( arr, arr+n );
        

        if(n == x ) cout << 0 << endl;
        else cout << arr[n-x] - 1 <<endl;

	 }
	return 0;
}

whats making this code fail the tests?

3

The Problem is you are printing 0 when n equals x which is not possible for
n=2,x=2;
2 5 See here the Passing Marks Will be 1 but as per your code, it will still give 0.
You can simply cout<<arr[0] -1; as the array is sorted which will provide you with the correct Solution

Welcome :slight_smile: