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

Problem 466C Help
Автор aakarshmadhavan, история, 6 лет назад, По-английски

466C

This is problem 2 from Ahmed Aly's Div-C ladder. I got the O(N^2) solution easily but it did time out so I am thinking of some ways to go for the O(N) solution. I believe it will involve dynamic programming similar to knapsack.

I just need some hints, is this correct?

Thanks

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

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

I would follow another path of thinking, but it is up to you.

First think of simpler problem, what if there were no zeros in the input? How would you find the solution, and what values can this be?

Hint

Now consider if there are zeros. We can do something similar, and if the partitions/cuts of the array fall are next to zeros we use math/multiplication counting.

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

    How about the case with negative numbers?

    If there were no zeros (and only positive numbers) I would basically cut everytime I got (SUM_OF_ARRAY/3).

    But with {-1, +1} somewhere there this will make things tricky.

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

      Maybe you can make a binary array based on when prefix sum is 2S/3, then construct a suffix sum array based on it. (a[i] += a[i+1])

      Then loop every s/3 and add the suffix sum at the point to your answer.

      This should be O(n)

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

Okay, first of all the sum of elements in the array must be a multiple of 3.

How many options do we have for the first part ?

Any i, where the prefix sum (i) = S / 3

How many options do we have for the third part ? __ Any j, where suffix sum (j) = S / 3

Notice that if we have chosen such an i and j then the middle part is forced to be S / 3 as well.

This can be done in O(n2) time. How do we improve it to O(n) ?

Precompute for each i, the number of j > i such that Suffix sum (j) = S / 3

Here is some explanation and some code.

→ Ответить