MOVIEWKN - Editorial

PROBLEM LINK:

Practice
Contest

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.

Possible bugs: There are no bugs of that type in this question as 1 ≤ Li, Ri ≤ 100. But this is useful for newbie.

@ankurverma1994: Oh, you are right. I had some older version in the mind. Thanks, I have corrected. :slight_smile:

1 Like

Hello,

I have completed my code and I thinks its right… but after submitting it… the answers is wrong…
Can Someone help me??

@ssingh15 Your logic is correct, but your code is getting WA cause, you have to strictly adhere to INPUT and OUTPUT Format mentioned.

You cannot input/output statements like “Enter the number of movies that you have on a weekend:” or “The movie to watch is of index:”.

Please watch other solutions. Hopefully you will realise your mistake.

You are such an amazing formula posting to this blog I am save your article link because I hope you article its very helping out for me in future anyways thank you so much. Sam Winchester Jacket Instylejackets

So interesting! Thanks a lot!
Essay Ninja

//