kingjohn123's blog

Help with Hackerearth Problem
By kingjohn123, history, 5 years ago, In English

I came across this problem on HackerEarth and I don't know how to go about the solution. Can anyone help?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Why tf people are downvoting blog & instead upvoting stories about softwares engineers .

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Constraints ? And it is better to give link rather than picture , as link assures that it's not from ongoing contest.

→ Reply
»
5 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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.

→ Reply