PROBLEM LINK:
Author: Sergey Kulik
Testers: Vasya Antoniuk and Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
Simple
PREREQUISITES:
Loops
PROBLEM:
N students will take E exams. All the students with score strictly greater than at least (N-K) students’ total score pass. Each exam’s score is an integer between 0 and M, inclusive.
They have already taken E-1 exams. Sergey is the N th person. Given that he knows the results of the other N-1 students in the remaining exam, what is the minimum score he must have to pass? (or determine if it is impossible to pass.)
QUICK EXPLANATION:
- Find all total scores of the first N-1 students, and sort them in increasing order. Let the (N-K)'th smallest total be x.
- Let y be the total score Sergey in the first E-1 exams.
- Then Sergey needs at least \max(0, x - y + 1) points. If this exceeds M, then the answer is
Impossible.
EXPLANATION:
Sergey passes if and only if his total score is strictly greater than the (N-K)'th smallest total score. So the answer consists of two parts:
- Computing the (N-K)'th smallest total score, and
- Finding the smallest number of points for Sergey to exceed this total score.
The first part can easily be done by first computing the N-1 total scores of the other students using a nested loop, and then sorting. The (N-K)'th element of the sorted array is what we want! This runs in O(N \log N + NE) time, but we also note that this can be reduced to just O(NE) by using a linear-time selection algorithm.
For the second part, suppose the (N-K)'th smallest total is x, and Sergey’s total score in the first E-1 exams is y. (y can be computed with a simple loop). Then we must find the minimum score which, when added to y, becomes strictly greater than x. If y > x already, then this is 0. Otherwise (i.e., if y\le x), then we need to find an integer T such that y + T > x. Clearly this is minimized if the sum is as small as possible, but the smallest integer > x is x + 1, so y + T must be equal to x + 1. Thus, T = x - y + 1. Finally, note that an exam score is at most M, so we must check if T \le M, because if T > M, then we conclude that Sergey will not pass.
Here’s an implementation of this algorithm in C++:
#include <iostream>
#include <algorithm>
using namespace std;
long long totals[10011];
// select the I'th smallest element from totals[0]...totals[N-1]
long long select(int N, int I) {
sort(totals, totals+N);
return totals[I-1];
}
int main() {
int T;
cin >> T;
for (int cas = 1; cas <= T; cas++) {
int N, K, E, M;
cin >> N >> K >> E >> M;
for (int i = 0; i < N-1; i++) {
long long total = 0;
for (int j = 0; j < E; j++) {
long long score;
cin >> score;
total += score;
}
totals[i] = total;
}
long long x = select(N-1, N-K);
long long y = 0;
for (int j = 0; j < E-1; j++) {
long long score;
cin >> score;
y += score;
}
long long answer = max(0LL, x - y + 1);
if (answer > M) {
cout << "Impossible" << endl;
} else {
cout << answer << endl;
}
}
}
Note that we don’t store the individual exam scores. Rather we compute the total of each student on the fly, and just store the totals.
Time Complexity:
O(N \log N + NE)