I never understand when someone asks questions like this. Isn't it more interesting to figure it out yourself?

I have updated it in the post. What do you mean by feedback?

Same here

Same here.

Working now.

Keep calm and press F5

I submitted 20 minutes ago, still processing.

I get these for a change.

hackerrank.com/environment
1 exception C/C++ is 1sec in most of challenges.

i got 80 using sqrt-decomposition.

also stupid sqrt-decomposition got 92(!!! O.o) on Set queries, but i submitted it after contest finished(

I guess all problems of this kind can be solved using segmenet tree or even fenwick tree. I solved it using segment tree.

When we add an interval [x, y] then in fact we add log(n) align intervals which corresponds to our nodes in segment tree. On each align interval [a, b] we add sth like (k + 1)(k + 2), (k + 2)(k + 3), ..., (k + (b - a) + 2)(k + (b - a) + 3).

We keep four numbers in each node:

• sum of actual values on this interval

• number of k mention above

• sum of k mention above

• sum of k² mention above

And we use lazy propagation. U can find similar task with good editorial here http://lbv-pc.blogspot.com/2012/11/rip-van-winkles-code.html

I solved it by Segment tree, {1 * 2, 2 * 3, 3 * 4, 4 * 5...} = {1, 3, 6, 10, 15...} * 2 = {1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5, ...} * 2

for each vertex in segment tree I save 3 value: first element,Difference,and difference of differences,here my code with easy "lazy propagation".

you can solve it with Fenwick tree by first calculating: sum(i = x to n) (x — i + 1) x (x — i + 2) , you will get a polynomial of degree 3, then you can use four BITs to heep all necessary information.

I got a full score with the same time complexity(but in my solution the extra logarithm arises from a binary search). I know how to get rid of it, so O(N * sqrt(N)) is possible.

Almost the same here, but I tried different boundaries to divide subset into heavy and light, turns out 317 gets 82 pts and 200 gets 91 pts. Really interesting.

Did you get away with all of them?

Roughly in <=2 weeks you will get an email about claiming AWS 100$.

Lio Se, Seoul, Korea, Republic of

Actually, they didn't send anything to Russia at all for a while

There has been trouble sending Tshirt to Belarus and Russia. We try to resolve that by sending to any alternate contact in USA for example.
Will still try and find a solution to this problem.

Instead of updating the nodes/subtrees on the path from a to b, we can do three separate updates. First and second start from a and b respectively, and finish at the root. The third one is similar but it starts from , and we update  - 2t instead. For the "upper part" queries we must update all nodes on the path to the root, but for the "lower part" queries, we only need to remember how much it got updated with an integer f_i, and increase it by t or  - 2t.

Denote P(u) as the sum we would get, if we walk from u to the root, and add the subtree sizes of each node we encounter . This is similar to the idea of prefix sums, and is needed for handling the "lower part" queries, as we are required to calculate the following sum for each query on the "lower part" of u:

Calculating this sum can be done with two segment trees storing P(v)·f_v and f_v respectively.

HLD can answer the query over subtree, HLD is a DFS order, so all the node of a subtree occupy a continuous range(U already knew that :) ).

And for Ur second question, we update a segment on segment tree, we don't care about the size of each node in the segment, since we are adding the same value to all of them and we want the sum of a segment in segment tree. So we can store the sum of size of all the mode in a segment and the value we add to the segment, then we know the answer is sum of size multiply by sum of value.

I am the setter of Epic Tree challenge. First, you are right about that part of editorial. I have tried to explain how to do such update with segment tree, but I could not manage to do it. It is hard to explain, but you can check my implementation. It is easier to understand in that way.

Secondly, When you traverse the tree with DFS you get an order of the tree. Let's call it DFS order. With DFS order you can do HLD. In the meantime you guarantee that all nodes in the subtree of node X has contiguous numbers. So you can easily query that subtree.

Recurrence relation of Kadane's algorithm is F_n = Ar_n + max(F_n - 1, 0). It gives the value of maximum sum of segments that end at index n. However, this problem asks for the value of 2 segments not 1, so recurrence relation is not the same but really similar: F_l, r = Ar_l * Ar_r + max(F_{l + 1, r - 1}, 0). F_l, r is the maximum value of 2 segments where left one begins at index l and right one ends at index r. Then, you need to get maximum of F_l, r for different (l, r) pairs.

Here is my code.

The only different thing in the editorial is that the implementation is bottom-up.

MY CODE FOR ALL PROBLEMS.

All except set queries problem get full scores. I got 91 pts on set queries.

I found a very similar solution . my low score was because I was not using comparator . like this code it . Isn't normal sorting according to the rules made by this comparator ? Help me :(

yes. You should've received email from hackerrank with link "Redeem your $100 worth of AWS Services here by July 12th"