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

Pls help in this problem -
Автор 650iq, история, 8 месяцев назад, По-английски

https://mirror.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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

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$$$.

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

    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://mirror.codeforces.com/contest/1155/submission/252016885 For the example u gave it is indeed returning 6

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

      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$$$.

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

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

        → Ответить