### Loserinlife's blog

By Loserinlife, history, 12 months ago,

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.

• 0

 » 12 months ago, # |   0 Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).
 » 12 months ago, # |   0 Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).
 » 12 months ago, # |   0 Any link?
•  » » 12 months ago, # ^ |   0 I don't have one. It's an offline competition. (It could be impossible for all I know)
 » 12 months ago, # | ← Rev. 2 →   0 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, # ^ |   0 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, # |   +12 I think it's unsolvable under the given constraints (it looks harder than FFT).
•  » » 12 months ago, # ^ |   +3 I will try to ask my friend to reach the authors :)). Thanks
 » 12 months ago, # |   +17 do you mean ∑abs(ai)<=1e6?
•  » » 12 months ago, # ^ |   0 The original problem says for a single element ai. But the problem itself is probably wrong.
•  » » » 12 months ago, # ^ |   +19 Can you ask them the solution? If they have any of course.
•  » » 12 months ago, # ^ | ← Rev. 4 →   -12 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, # ^ |   0 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 nI'm not sure is there sth I missed.
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   +1 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 →   0 oh ! oh ! you are right.Single fft cannot distinguish positive and negative perfixwhy are there so many downvotes in your comments? The community not know the correct answer