# MOVIEWKN - Editorial

Author: Constantine Sokol
Tester: Pavel Sheftelevich
Editorialist: Praveen Dhinwa

cakewalk

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.

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:”.

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

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.

1 Like

Weak test cases. I think there is no test cases for check if only l[I]*r[I] is maximum. I think you can add below test case also:
For input
1
2
1 3
2 1

Output expected should be:
2

Just for comparison what I am trying to point out, attaching two program links which gives different output for above input but both are excepted.
Wrong one --> https://www.codechef.com/viewsolution/32162015
Correct one --> https://www.codechef.com/viewsolution/32161783

what for 1
2
1 4
2 1
my accepted solution gives : index 1,but correct answer is 2.
anyone?? @dpraveen @sgrpwr @ankurverma1994 @lohit_97
help pls