If you want to directly access the problem you can click here
Problem Statement
You are given array a of n integers. You need to split the array into 2 arrays (one of which may be empty) such that sum of product of these 2 arrays is maximum.
Formally, you need to find l such that sum of a1⋅a2⋅⋯⋅al and al+1⋅al+2⋅⋯⋅an is maximum over all valid choices for l.
Note that an empty array has a product of 0.
Output
Print the maximum sum of product of the arrays mod 1e9+7.
Constraints
1≤n≤1e5 , 1≤|ai|≤1e9
I tried to solve this problem by pre-calculating prefix product and suffix product modulo M(1e9+7) and taking the maximum among every i (1<=i<=n).But still its showing me WA for large inputs of a[i]. Can anyone suggest me where am I making a mistake ?
Thanks in Advance.
Auto comment: topic has been updated by _Chaitanya1999 (previous revision, new revision, compare).
(x % n) >= (y % n) doesn't imply x >= y
Comparing two numbers modulo M is a bad idea, because it can and almost certainly lead to wrong results: for example, let's compare 2 and 1e9 + 8. Obviously, 2 < 1e9 + 8, but if you were to compare these numbers in modulo 1e9 + 7, you get 2 > 1, so you get that 2 > 1e9 + 8.
Instead of using modulo, you can calculate these prefix and suffix products under a logarithm, so instead of storing the product itself, you store its logarithm. This way, you can still correctly compare these numbers by comparing their logarithms.
How do you store a negative number in some base's exponent? isn't the exponent a complex number?
Since you can determine the sign of the product just by looking at how many negative numbers there are, you can take the logarithm of the absolute value (i. e. $$$ |a[i]| $$$), then you just look at the number of negative numbers to find out the sign of the product.
But exponents may be fractional. I mean won't there be any precision issues?
If you use
long double, which allows a precision of at least 19 decimal places, it should be OK.Im not sure but it looks like you need take a whole array except cases a[0] == 1 || a[n — 1] == 1
I think you're right.
Let P(i,j) indicate the prodoct from ai to aj.Then if there exist a L which make P(1,L)+P(L+1,n)>P(1,n) hold, we can get 1/P(L+1,n) +1/P(1,L) > 1 by dividing P(1,n).
Since even 1/2 + 1/2 = 1, inequality above holds if and only if P(1,L)==0||P(L+1,n)==0.
it's not absolutely right bcs we have negative numbers (didnt see it before). so we need check some cases when cnt_of_negative is over or odd
Not see it before too lol
If the product of all elements is positive, your ideia works, because if a[0] > 1, its obvious better to put a[0] in the product, if a[0] < 0, if we remove a[0] of the product, the answer become negative, so the only case that worth remove a[0] is when a[0] = 1,(the same logic works for a[n-1]).
If the product of all elements is negative, i thought in this ideia:
Let $$$a_i$$$ be the first negative element of the array, and $$$a_j$$$ be the last negative of the array.
Let $$$B = a_1 \ * \ ... \ * \ a_i$$$, $$$C = a_j \ * \ ... \ * \ a_n$$$
The answer will be $$$a1 \ * \ ... \ * \ a_{j-1} + C$$$ if $$$|B| >= |C|$$$,
or $$$B + a_{i+1} \ * ... \ * \ a_n$$$, otherwise.
However i don't know to compare B and C because of the mod, maybe my ideia is completely wrong.
to compare u can calculate product under a logarithm, so instead of storing the product itself, you store its logarithm.
i tried logarithm, i got WA (i can't see if its was really a WA instead of other erro).
There was a bug in my code. I got AC with my ideia using logarithm after solved the bug.
If I click the original problem link, it says "Not allowed to view the contest".
oops my bad! You have to register so that u can access the problem You can register here now if u like to.
My code for this problem https://ideone.com/bHjauL
_Chaitanya1999 what's the solution? I saw you got AC.
UPD: I get AC
Can you share your code?
Thats the link submision: [submission:105025756].
If you can't see the submission (i don't know how gym works):