Блог пользователя _Chaitanya1999

Автор _Chaitanya1999, история, 3 года назад, По-английски

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. 
  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +23 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Not see it before too lol

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

UPD: I get AC

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you share your code?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thats the link submision: [submission:105025756].

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

      Spoiler