Bound on the number of different sums of consecutive elements in an arbitrary array

Revision en2, by beginner1010, 2019-08-26 03:36:43

Today, I tried F2. Same Sum Blocks (Hard) from Codeforces Round #547 (Div. 3). 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 consecutive 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)