ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1560. Elementary Symmetric Functions

Hint?
Posted by fantasy 24 Sep 2007 17:27
Could you please give me some hints? All my submissions get the same answer "time limit exceeded".
Re: Hint?
Posted by svr 24 Sep 2007 19:40
Cumulative Frequency Tables
Re: Hint?
Posted by ntmquan 24 Sep 2007 21:15
Can you explain it more concretly?With me,  "Cumulative Frequency Tables" looks strange.
Re: Hint?
Posted by svr 24 Sep 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
Re: Hint?
Posted by ntmquan 24 Sep 2007 22:35
Thanks
Re: Hint?
Posted by Vedernikoff Sergey 25 Sep 2007 18:09
I think it is more usual to use Fenwick trees
Re: Hint?
Posted by svr 27 Sep 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
Re: Hint?
Posted by Vedernikoff Sergey 29 Sep 2007 03:25
For using Fenwick trees you also need only array, and, moreover, only one array!
Re: Hint?
Posted by Denis Koshman 15 Aug 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).
Re: Hint?
Posted by Aditya Sheth 18 Jul 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.