RATING - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Lavish Gupta
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef really likes to compete on Codechef, and he has gained an impressive rating of X, where X \gt 0. There is also a parallel universe, where ratings on Codechef are negative instead. The only thing that remains unchanged in the parallel universe is Chef’s love for competing on Codechef. Chef’s rating on Codechef in the parallel universe is Y, where Y \lt 0.

Due to some cosmic event, the parallel universe has been destroyed, resulting in Chef forgetting both X and Y. He only remembers the sum S = X+Y. He wonders what the maximum possible product of his ratings is, given that he knows the sum of his ratings.

EXPLANATION:

The mathematical crux of the problem

We have two variables X and Y, such that X \gt 0 and Y \lt 0. We don’t know the exact values of X and Y, however, we know the value of their sum S = X+Y. Given the sum, we want to maximize the product, that is X \cdot Y.

What are the possible values of (X, Y)?

We have X + Y = S \implies X = S - Y. Now note that S \geq 0, and Y \lt 0. This guarantees that X = S - Y will always be greater than 0 for all valid values of Y. If we start with Y = -1, and further decrease Y, the values of (X, Y) that we will get will look like this: (S+1, -1), (S+2, -2) or in general, (S+r, -r), r \gt 0.

What happens when X increases?

So our product is X \cdot Y. Now, as X increases, Y decreases, but note that Y \lt 0, so Y decreases, but increases in magnitude. As a result, the product increases in magnitude, but because there is a negative sign, the product decreases as X increases.

The final answer!

We have seen that as X increases, the product decreases. So we should take the minimum value of X, which is S+1, to maximize the product. For this X, Y = -1, and therefore the maximum product will -(S+1).

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Editorialist's Solution 
#include<bits/stdc++.h>
using namespace std ;

int main()
{
    int t ;
    cin >> t ;

    while(t--)
    {
        int s ;
        cin >> s ;
        cout << -1*(s+1) << endl ;
    }

    return 0;
}
3 Likes