I came across this problem on HackerEarth and I don't know how to go about the solution. Can anyone help?
# | User | Rating |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
# | User | Contrib. |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 154 |
9 | Petr | 146 |
10 | djm03178 | 145 |
I came across this problem on HackerEarth and I don't know how to go about the solution. Can anyone help?
Name |
---|
Why tf people are downvoting blog & instead upvoting stories about softwares engineers .
Constraints ? And it is better to give link rather than picture , as link assures that it's not from ongoing contest.
Hey, yes so sorry will keep that in mind. Here is the link
https://www.hackerearth.com/challenges/competitive/pycon-2020/algorithm/jumbo-and-array-1-69b5c314-2b740e3b/
Here's your solution
We can make 2 segment/fenwick trees , one for A[i] and another for (A[i])^2 .
Now 2nd query is a trivial point update query
now for first query you should notice that the given formula can be written as
((A[L]+A[L+1]+A[L+2]+....+A[R])*(A[L]+A[L+1]+A[L+2]+....+A[R]))/2 — (A[L]^2+A[L+1]^2+A[L+2]^2+....+A[R]^2) . Again it's just range sum query on segment/Fenwick tree
I think the correct formula is ((A[L]+A[L+1]+A[L+2]+....+A[R])*(A[L]+A[L+1]+A[L+2]+....+A[R]) — (A[L]^2+A[L+1]^2+A[L+2]^2+....+A[R]^2)) / 2
Oh yeah it's this , My mistake ':)
This Problem is pretty much easy if you use a segment tree.
Suppose the left child node contains answers for range [A1, A2] and the right child node contains answers for range [A3, A4] then the parent node must contain the answers for range [A1...A4] which can be obtained from the values of left child node and right child node.
Let, left child node holds, L1 = answer for their subtree [Ex:- A1, A2] L2 = subtree sum [Ex:- A1 + A2]
and, right child node holds, R1 = answer for their subtree [Ex:- A3, A4] R2 = subtree sum [Ex:- A3 + A4] Then, answer for parent node will be :- Ans = L1 + R1 + L2*R2.
The extra term L2*R2 comes because we want every element present in the left child range to form a product with every element in the right child range which in turn comes out to be L2*R2 (do some pen and paperwork, you will get that).
So, Each node of the segment tree stores two data, answer as well as the sum in their range.
Note:- I got my solution accepted in the last minute of the test.