_Chaitanya1999's blog

An Interesting Problem...Help Needed!
By _Chaitanya1999, history, 5 years ago, In English

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.
  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (22)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by _Chaitanya1999 (previous revision, new revision, compare).

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it +23 Vote: I do not like it

(x % n) >= (y % n) doesn't imply x >= y

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

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.

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Im not sure but it looks like you need take a whole array except cases a[0] == 1 || a[n — 1] == 1

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        5 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Not see it before too lol

        → Reply
      • »
        »
        »
        »
        5 years ago, hide # ^ |
        ← Rev. 3  
        Vote: I like it 0 Vote: I do not like it

        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| \gt = |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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          to compare u can calculate product under a logarithm, so instead of storing the product itself, you store its logarithm.

          → Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it +20 Vote: I do not like it

If I click the original problem link, it says "Not allowed to view the contest".

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

My code for this problem https://ideone.com/bHjauL

→ Reply
»
5 years ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

_Chaitanya1999 what's the solution? I saw you got AC.

UPD: I get AC

→ Reply
  • »
    »
    5 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Can you share your code?

    → Reply
    • »
      »
      »
      5 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Thats the link submision: 105025756.

      If you can't see the submission (i don't know how gym works):

      Spoiler
      → Reply