Loserinlife's blog

Count the most common occurrence of subarray sum.
By Loserinlife, history, 3 years 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 (12)
| Write comment?
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Any link?

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    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
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +19 Vote: I do not like it

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

      → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← 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 \lt j$$$, and iirc this is only possible with FFTs of total length $$$O(m \log m)$$$.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        3 years ago, hide # ^ |
        ← 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