PROBLEM LINK:
Author: Constantine Sokol
Tester: Pavel Sheftelevich
Editorialist: Praveen Dhinwa
DIFFICULTY:
cakewalk
PREREQUISITES:
None
PROBLEM:
You want to select a movie to watch on the weekend. There are n movies in cinema : i-th of them has rating R_i and length (duration) L_i. You want to select a movie according to following criterions applied in order.
- First you choose a movie with highest value of L_i * R_i.
- If there are more than one such movies, you select the one with the highest rating R_i.
- If still, there are more than one such movies, you select the one with the minimum index i.
You have to output the index of movie (1-based) that you are going to watch.
QUICK EXPLANATION:
Just implement what is said in the problem statement.
EXPLANATION:
Let us iterate over i from 1 to n. Let max_{LR} denote the the maximum value of L_j * R_j till now (i.e. for all j < i). Similarly, let maxR denote the maximum rating R_j among all the movies such that L_j * R_j = max_{LR}, j < i. Also, let ans denote the index corresponding to the movie you should select till now to watch. Now, we want to consider the i-th movie and want to find the what would be the best movie you select to watch after considering i-th movie.
There are following possible scenarios.
- If L_i * R_i < max_{LR}, then this movie can not be the best movie to watch. So you skip this movie.
- If L_i * R_i > max_{LR}, then this movie will be the best movie to watch till now. Update max_{LR} to L_j * R_j and maxR to R_i.
- If L_i * R_i = max_{LR}, then it means that current movie might be a possible best movie to watch. We should now check the second criteria : i.e., whether the rating of current movie is strictly greater than max_R or not. If yes, then we will select this movie to be the best movie till now. Otherwise, if rating R_i of this movie is equal to max_R, then we will go to third criteria and check whether the index of this movie is less than ans or not. Note that this can never be possible, because we are going in increasing order of indices. So, we don’t even need to consider this case.
At the end of the iteration, ans will be the index of best movie to watch.
Pseudo Code
long maxLR = 0;
long maxR = 0;
int ans = 0;
for (int i = 1; i <= L.length; i++) {
if (L[i] * (long) R[i] > maxLR) {
maxLR = L[i] * (long) R[i];
maxR = R[i];
ans = i;
} else if (L[i] * (long) R[i] == maxLR) {
if (R[i] > maxR) {
maxR = R[i];
ans = i;
}
}
}
print ans
Time complexity:
We iterate over the arrays L, R only once. Hence time complexity is \mathcal{O}(n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
