Bound on the number of different sums of continuoussecutive elements in an arbitrary array
Difference between en1 and en2, changed 22 character(s)
Today, I tried [F2. Same Sum Blocks (Hard) from Codeforces Round #547 (Div. 3)](https://codeforces.com/problemset/problem/1141/F2). Since $n$ can be as large as $1500$, I was struggling to come up with an $O(n^2)$ but I failed.↵

When I read the editorial, surprisingly, I found out that the writer's solution is $O(n^3)$. They used a `Hashmap` to speedup the whole process, and it seems that the number of different summation values of con
tinuoussecutive elements will be less than $n^2$. Though I cannot find any counterexample such that different sub-array sums can be as large as $n^2$ (or at least as large as $\frac{n \times (n - 1)}{2}$), I cannot convince myself an $O(n^3)$ approach can pass the system test.↵

I was wondering if you have any analysis to demonstrate that the optimization (using `Hashmap`) is sufficient, or if you know any bound on the number of different summation of consecutive elements in an arbitrary array.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English beginner1010 2019-08-26 03:36:43 22 Tiny change: 'ues of continuous elements ' -> 'ues of consecutive elements '
en1 English beginner1010 2019-08-26 03:35:18 1015 Initial revision (published)