650iq's blog

By 650iq, history, 2 months ago, In English

https://codeforces.com/contest/1155/problem/D

This problem is similar to yesterdays atcoder regular contest problem A, where i used the logic that if X>0 we multiply the maximum segment and if X<0 we multiply the minimum segment but if i use the same logic in this question it is giving WA on test 10. Can someone pls help me understand why it doesn't work here?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This logic would've worked for $$$x>0$$$, but may not work for negative values of $$$x$$$, since in these scenarios, it may be more beneficial to multiply a segment of the chosen subarray instead.

For instance, consider the array $$$a = [2, -2, 2]$$$ and $$$x = -1$$$. The minimum subarray in $$$a$$$ would be $$$[-2]$$$, and the answer derived would be $$$-2\times -1 = 2$$$. However, a more optimal solution would be to multiply the $$$-2$$$ by $$$-1$$$ and choose the entire array (which is now $$$[2, 2, 2]$$$) to be summed, yielding a result of $$$6$$$.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't got the example part in both the scenarios u are multiplying -2 with -1 only right? What I'm doing is im finding the minimum sum subarray and multiplying it with X and then again running kadanes algo on top of that https://codeforces.com/contest/1155/submission/252016885 For the example u gave it is indeed returning 6

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry for misunderstanding your algorithm. However, the maximum sum obtainable using this algorithm may still not be optimal.

      For instance, consider the following example: $$$a = [5, -6, 7, -9]$$$ and $$$x = -1$$$. After the transformation, $$$a$$$ would equal $$$[5, -6, 7, 9]$$$, where the optimal sum is $$$7+9=16$$$. However, a better solution in this case is to multiple $$$[-6]$$$ instead, yielding $$$[5, 6, 7, -9]$$$ whose maximal subarray sum is $$$18$$$.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Right got it.. so basically finding the max subarray after transformation makes this question difficult Thanks:)