aakarshmadhavan's blog

By aakarshmadhavan, history, 6 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

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

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

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

      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 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.