GUMP - Editorial

PROBLEM LINK:

Practice Link

Contest Link

Author: Ankush Khanna

DIFFICULTY:

Easy-Medium

PREREQUISITES:

AM-GM Inequality, Modular Arithmetic, Modular Inverse, Fast Exponentiation, Fermat’s Little Theorem, Mathematics

PROBLEM:

Given the size N of a sequence of numbers, and the sum S of that sequence, find the maximum product of this sequence, and print it modulo (10^9 + 7).

QUICK EXPLANATION:

Key to AC: The answer to this problem is \big ( \big ( \frac {S} {N} \big )^{N} \bmod (10^9 + 7) \big ) \space, using AM-GM Inequality. Here, using modular arithmetic, we can find the modular inverse of N^N \bmod (10^9 + 7) \space, using techniques like Fermat’s Little Theorem and then do modular multiplication with S^N \bmod (10^9 + 7). Everything is explained in detail in the explanation part.

EXPLANATION:

Let’s first see what all Mathematics we need to know in order to solve this problem. Let’s, for the sake of comfort, name the sequence as A. First of all, let me state the problem mathematically,

You are given with S = \bigg( \sum \limits_{i = 1}^{N} A_i \bigg), and it is also mentioned that N and S are positive integers and that N \leq S.

Also, A_i \gt 0, for each valid i and A_i is a number.

Now, you need to maximize a number \space P, such that P = \bigg ( \prod \limits_{i = 1}^{N} A_i \bigg ).

Now, first understand what AM-GM inequality is, and why is it important here. It is stated mathematically as:

\frac {\sum\limits_{i = 1}^{N} A_i} {N} \geq \bigg (\prod\limits_{i = 1}^{N} A_i \bigg)^{\big(\frac {1} {N}\big)}

\implies \frac {S} {N} \geq \sqrt[N]{P}

\therefore \big (\frac {S} {N} \big )^N \geq P

i.e., Arithmetic Mean (AM) \geq Geometric Mean (GM), and both of them are equal if and only if for each valid pair (i, j), \space A_i = A_j, \space where \space i \neq j (which is the condition for GM to be maximum possible)

\therefore \space to keep the product maximum, we will keep all the elements of A equal.

\therefore \space P = \big (\frac {S} {N} \big )^N ( maximum possible value of P \space )

\implies \space A_i = \frac {S} {N} (which is the Arithmetic Mean), for each valid i

Also, one needs to understand that integers are different from numbers. Numbers can be anything. They can be integer, fraction, irrational, real, complex, etc.
But, here, it can be proved that P is always a rational number and can be expressed in the form of \frac {X} {Y}, \space Y \neq 0 and both X and Y are positive integers. It is very clear here, we don’t even need to explicitly prove it, it can be seen easily in our derived expression for P. [Integers and Numbers]

Now, it is mentioned that we need to print the answer modulo 10^9 + 7 (smallest 10 digit prime number). Therefore, we need to do something like:

(S^N \bmod (10^9 + 7) \times modularInverse(N^N) \bmod (10^9 + 7)) \bmod (10^9 + 7)

A basic understanding of modular arithmetic is a must for this problem. One must be clear about the rules of modular arithmetic, before attempting this problem.

We can easily do modular exponentiation in O(\log_2 N) time complexity. We can easily find the Modular Inverse of N^N using Fermat’s Little Theorem in O(\log_2 M) time, where M is a prime and M = 10^9 + 7. And, it can also be proved that, gcd(N^N, \space M) = 1, as N \lt M, and M is a prime, \therefore \space N^N can never have any common divisor with M, which is a mandatory condition for modular multiplicative inverse to exist and be unique.

Sub-Task 1

It is given than S = \alpha \times N, where \alpha is a positive integer.

\implies \space We don’t need to find the modular inverse, \because \space \alpha = \frac {S} {N}, so just printing (\alpha^N \bmod (10^9 + 7)) \space will get you 10 points. Time taken per test case would be O(\log_2 N) with O(1) auxiliary space.

Sub-Task 2

Can be solved as mentioned above in the explanation part.

Final Result = (S^N \bmod M) \times ((N^N \bmod M)^{(M - 2)}) \bmod M, where M = (10^9 + 7)

\{ According to Fermat’s Little Theorem, modularInverse(X) \mod Y = X^{(Y - 2)} \bmod Y \space \}

COMPLEXITY:

O(\log_2 N + \log_2 M) time per test case, where M = 10^9 + 7, with O(1) auxiliary space used.

\therefore total time for each test file would be O(T \times (\log_2 N + \log_2 M)) \space, which would suffice our time constraint.

SOLUTION:

Setter’s Solution [Plain Text]

Feel free to share your approach. If you have any queries, they are always welcome.

1 Like

this my code. but I’m getting WA.But i cann’t understand why?
My logic:

the maximum ans will be x^n where
x=(s/n)
but if x%n!=0
then I increase Y x by one
where
y=s%n;
now the maximum ans will be x^(n-y)*(x+1)^y

Can anyone tell me why I am getting WA?Is my logic is wrong?If wrong,then why?
Can you provide a test case for which my code will give WA?

Thanks in advance :slightly_smiling_face::slightly_smiling_face:

When N divides S, we have the answer as \bigg[\Big(\frac{S}{N}\Big)^N \bmod (10^9 + 7)\bigg]. That part is absolutely correct, and it fetches us the points for the first subtask.

For the case when N does not divide S (which happens in the second subtask), we still need to follow the AM - GM Inequality law strictly, and make use of modular inverse for evaluating the fractional part, that is \Big(\frac{1}{N}\Big)^N under modulo (10^9 + 7). It is well mentioned in the editorial of this problem as well. And explanation is also provided.

Here’s a good test case to check:
When N = 3 and S = 5, your code will do it like this:
\bigg(\big\lfloor\frac{5}{3}\big\rfloor^{(5 - (5 \bmod 3))}\bigg).\bigg(\Big(\big\lfloor\frac{5}{3}\big\rfloor + 1\Big)^{(5 \bmod 3)}\bigg) = 1^3.2^2 = 4
This is an incorrect way to determine the answer, because you are calculating it incorrectly. This formula, though works for the first subtask \because S \bmod N is always 0 there, will always produce incorrect results when S \bmod N \gt 0, because this formula disregards the actual fraction, and evaluates the answer using a rounded down integer, which should not be the case as it is nowhere mentioned it the problem statement.
The correct sequence for this case is \Big(\frac{5}{3}, \frac{5}{3}, \frac{5}{3}\Big) and hence the product is \frac{5^3}{3^3} = \frac{125}{81}. Also, we have to print it modulo (10^9 + 7), so we use modular inverse for calculating \frac{1}{81} modulo (10^9 + 7). So, the correct answer for this case is 296296303. You can also refer to my solution provided in the editorial, and go through the editorial for further understanding the concept. This is a solution that I wrote just now - Solution (In this solution, I have first evaluated \frac{S}{N} \bmod (10^9 + 7) correctly using modular inverse \frac{1}{N} modulo (10^9 + 7) and then exponentiated it to power N, using fast exponentiation technique).

It’s just that the \LaTeX of this editorial is not getting rendered properly due to this new Discussion Panel. It was perfectly fine with the Old Discussion Forum. If you are facing problems reading the \LaTeX part, you can read this editorial on the Old Discussion Forum here, it’s still fine there. It’s a known bug and I had emailed the CodeChef team about it, about 2 months ago (April 2, 2019). They said they will fix it soon. Soon!

Hope you got it correctly. If you still have any doubts, do let me know.