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

Правка en1, от beginner1010, 2019-08-26 03:35:18

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 continuous 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский beginner1010 2019-08-26 03:36:43 22 Tiny change: 'ues of continuous elements ' -> 'ues of consecutive elements '
en1 Английский beginner1010 2019-08-26 03:35:18 1015 Initial revision (published)