PROBLEM LINK:
Author & Editoralist: Jafar Badour
Tester: Teja Reddy
PROBLEM EXPLANATION
Given the grades of 4*N students in the form of an array A[1\ldots4*N]. Set the boundaries for each letter grade (A,B,C,D) such that the number of students having any letter is exactly N.
You need to find x,y,z such that if:
0 \leq score \lt x means that grade is D
x \leq score \lt y means that grade is C
y \leq score \lt z means that grade is B
z \leq score \lt 100 means that grade is A
Find a solution that maximizes x+y+z or state that there’s no solution.
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
EXPLANATION:
Sort the students grades A[1 \ldots 4*N] according to their grades in ascending order.
The first N students should get D specifically students corresponding to grades A[1 \ldots N]
The next N students should get C specifically students corresponding to grades A[N+1 \ldots 2*N]
The next N students should get B specifically students corresponding to grades A[2*N+1 \ldots 3*N]
The next N students should get A specifically students corresponding to grades A[3*N+1 \ldots 4*N]
Formally speaking:
x=A_{N+1}
y=A_{2*N+1}
z=A_{3*N+1}
When we don’t have a solution? In any case that satisfies:
(A_{N+1}=A_N) OR (A_{2*N+1}=A_{2*N}) OR (A_{3*N+1}=A_{3*N})
Because the grades won’t be consistent with the boundaries.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int T , n , arr[200];
int main(){
cin>>T;
while(T--) {
cin >> n;
for (int j = 0; j < n; j++) {
cin >> arr[j];
}
sort(arr , arr + n);
int a = n/4 , b = a + a , c = a + a + a;
if (arr[a] == arr[a-1] || arr[b] == arr[b-1] || arr[c] == arr[c-1]) puts("-1");
else cout << arr[a] << ' ' << arr[b] << ' ' << arr[c] << endl;
}
return 0;
}