Loserinlife's blog

By Loserinlife, history, 12 months ago, In English

Count the most common occurrence of subarray sum.

Constraints:

N <= 1e6; abs(ai) <= 1e6

Ex:

Inp:

5

1 1 2 1 4

Out:

3 (there are 3 subarray with the sum of 4: (1, 1, 2), (1, 2, 1), (4)

This question appears in ones of my friends competition and I have no idea how to solve it. Can someone help? Thanks.

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any link?

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

    I don't have one. It's an offline competition. (It could be impossible for all I know)

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

Reminds me the problem: subarray sum equals k. U can solve this problem for each different sum and then check for which k the frequency Is maximized. For some small constraint It Will work. In pretty sure there Is some clever solution btw...

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

    Might be but for the worse, you can just solve it in n^2, since iterating for all the sums and kadanes is worse than n^2, I don't have idea for a better solution

»
12 months ago, # |
  Vote: I like it +12 Vote: I do not like it

I think it's unsolvable under the given constraints (it looks harder than FFT).

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I will try to ask my friend to reach the authors :)). Thanks

»
12 months ago, # |
  Vote: I like it +17 Vote: I do not like it

do you mean ∑abs(ai)<=1e6?

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

    The original problem says for a single element ai. But the problem itself is probably wrong.

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Can you ask them the solution? If they have any of course.

  • »
    »
    12 months ago, # ^ |
    Rev. 4   Vote: I like it -12 Vote: I do not like it

    Even if the sum of the values is small, isn't the solution $$$O(n + m \log^2 m)$$$ (where $$$m = \sum |a_i|)$$$? You have to compute only the differences such that $$$i < j$$$, and iirc this is only possible with FFTs of total length $$$O(m \log m)$$$.

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

      i didn't get why it was m log^2 m,

      i think i need here is a prefix sum, a convolution and an exclusion. it's n log n

      I'm not sure is there sth I missed.

      • »
        »
        »
        »
        12 months ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        The convolution actually calculates the most frequent absolute value of a subarray sum (each subarray contributes to two sums, with opposite signs). You need D&C if you only want sums with the correct sign.

        (What's an "exclusion"? Am I missing something?)

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
          Rev. 8   Vote: I like it 0 Vote: I do not like it

          oh ! oh ! you are right.

          Single fft cannot distinguish positive and negative perfix

          why are there so many downvotes in your comments? The community not know the correct answer