Обсуждение @ 1560. Elementary Symmetric Functions @ Timus Online Judge

fantasy Hint? [9] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 17:27

Could you please give me some hints? All my submissions get the same answer "time limit exceeded".

svr Re: Hint? [7] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 19:40

Cumulative Frequency Tables

ntmquan Re: Hint? // Задача 1560. Elementary Symmetric Functions 24 сен 2007 21:15

Can you explain it more concretly?With me, "Cumulative Frequency Tables" looks strange.

svr Re: Hint? [5] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 21:50

In my words:
It is 2^n type structure of data
with O(log) insert and O(log) interval-[left,right]
query in additive on subsets in [0,MAX] data,
easy to programming.
Best explanatuion in
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html

ntmquan Re: Hint? [4] // Задача 1560. Elementary Symmetric Functions 24 сен 2007 22:35

Thanks

Vedernikoff Sergey Re: Hint? [3] // Задача 1560. Elementary Symmetric Functions 25 сен 2007 18:09

I think it is more usual to use Fenwick trees

svr Re: Hint? [2] // Задача 1560. Elementary Symmetric Functions 27 сен 2007 14:08

Now I confirmed Cumulative Frequency Tables and ideas of
http://www.chiark.greenend.org.uk/~sgtatham/algorithms/cumulative.html
practically having AC 1.37 not very bad because used iostream. Tables better than Fenwick trees because they used
only arrays. For adopting the method I used
formulas a[k]=f(t0,t1,t2,...,tk) where tk=sum of A[i]^k
and is additive contrary to a[k].
During a long time had WA7 because forgotten
that abs does't work in __int64 and
we must build our own abs for __int64.

After cosmetic modifications have 0,843 Ac ant 3-th.
Edited by author 27.09.2007 14:24

Edited by author 27.09.2007 14:31

Edited by author 27.09.2007 14:51

Edited by author 27.09.2007 14:52

Vedernikoff Sergey Re: Hint? [1] // Задача 1560. Elementary Symmetric Functions 29 сен 2007 03:25

For using Fenwick trees you also need only array, and, moreover, only one array!

Denis Koshman Re: Hint? // Задача 1560. Elementary Symmetric Functions 15 авг 2008 16:21

I used 4 interval trees. One having Ai, another having Ai^2, another Ai^3 and the last one Ai^4. This way you can compute Al^k + ... + Ar^k in log(N) for k=1..4. This info is enough to calculate S(L..R, K).

Aditya Sheth Re: Hint? // Задача 1560. Elementary Symmetric Functions 18 июл 2020 16:50

It can be easily done using Segment tree. Try to store this s[0...4] for each node in segment tree. Now you can find a nice formula using convolution to merge two nodes.

Обсуждение задачи 1560. Elementary Symmetric Functions