| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
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.
Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).
Auto comment: topic has been updated by Loserinlife (previous revision, new revision, compare).
Any link?
I don't have one. It's an offline competition. (It could be impossible for all I know)
I think it's unsolvable under the given constraints (it looks harder than FFT).
I will try to ask my friend to reach the authors :)). Thanks
do you mean ∑abs(ai)<=1e6?
The original problem says for a single element ai. But the problem itself is probably wrong.
Can you ask them the solution? If they have any of course.
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)$$$.
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.
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?)
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