Loserinlife's blog

Count the most common occurrence of subarray sum.
By Loserinlife, history, 18 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

Comments Comments (13)
| Write comment?
»
18 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).

→ Reply
»
18 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).

→ Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any link?

→ Reply
  • »
    »
    18 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)

    → Reply
»
18 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).

→ Reply
  • »
    »
    18 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

    → Reply
»
18 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    18 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.

    → Reply
    • »
      »
      »
      18 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.

      → Reply
  • »
    »
    18 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)$$$.

    → Reply
    • »
      »
      »
      18 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.

      → Reply
      • »
        »
        »
        »
        18 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?)

        → Reply
        • »
          »
          »
          »
          »
          18 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

          → Reply