_Chaitanya1999's blog

An Interesting Problem...Help Needed!
By _Chaitanya1999, history, 4 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 (21)
| Write comment?
»
4 years ago, # |
  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
»
4 years ago, # |
← Rev. 2   Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  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
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    How do you store a negative number in some base's exponent? isn't the exponent a complex number?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

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

        But exponents may be fractional. I mean won't there be any precision issues?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          If you use long double, which allows a precision of at least 19 decimal places, it should be OK.

          → Reply
»
4 years ago, # |
  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
  • »
    »
    4 years ago, # ^ |
      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
    • »
      »
      »
      4 years ago, # ^ |
        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
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not see it before too lol

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← 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| >= |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
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            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
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            i tried logarithm, i got WA (i can't see if its was really a WA instead of other erro).

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

              There was a bug in my code. I got AC with my ideia using logarithm after solved the bug.

              → Reply
»
4 years ago, # |
← 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oops my bad! You have to register so that u can access the problem You can register here now if u like to.

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

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

→ Reply
»
4 years ago, # |
← 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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share your code?

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

      Thats the link submision: [submission:105025756].

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

      Spoiler
      → Reply