# Angry Children 2

# Angry Children 2

+ 3 comments After failing for test cases 8 and 9, I looked at editorial. It took a lot time to fully understand editorial.

I'll try to simplify mathematics.

Suppose Sorted Array is A : [1,2,3,4,5,6,7] S : [1,3,6,10,15,21,28] And K = 5

First, we need to find angry coefficient for first K items. This can be done in O(K)

Angry coefficient = Sum of i = 0 1 2 3 5-1 5-2 5-3 5-4 4-1 4-2 4-3 3-1 3-2 2-1 Clearly for each i there is a pattern. For i = 0, Sum(5,4,3,2,1) - Sum(1) - 4(1) For i = 1, Sum(5,4,3) - Sum(2,1) - 3(2) And so on. We already have a sum array. So this can be computed easily.

Now, we need to find the anger coefficient from k+1th term till last term.

We have already computed coeefient from 1 to 5. Now, we need to compute from 2 to 6 in O(1). Our previous coeffieint 5-1 5-2 5-3 5-4 4-1 4-2 4-3 3-1 3-2 2-1 Our new coefficient 6-2 6-3 6-4 6-5 5-2 5-3 5-4 4-2 4-3 3-2 These 2 tables have some items in common and some are different. We need to remove different items from old and add different items of new table. Items to add = 6-2 6-3 6-4 6-5 = 6(4) - ( Sum(5,4,3,2,1) - Sum(1) ) Items to remove 5-1 4-1 3-1 2-1 = ((Sum(5,4,3,2,1) - Sum(1)) - 1(4) So, new coefficient = Old + Items_to_add - Items_to_remove = Old + 6(4) - ( Sum(5,4,3,2,1) - Sum(1) ) - ((Sum(5,4,3,2,1) - Sum(1)) + 1(4) = Old + 4(6 + 1) - 2*(Sum(5,4,3,2,1) - Sum(1))

The rest if figuring out the code.

+ 0 comments I kind of have a problem with this constraint.

"0<= number of candies in each packet <=109"

Handing out a packet containing zero candies to a child seems needlessly cruel.

Plus it doesn't match to the first statement in the problem. A packet containing less than two candies is no longer a "packet of candies"

+ 1 comment Don't see why this is under Dynamic Programming.

+ 1 comment It's pretty stupid that I pay the 5 hackos to get test case 11.. and then I can't work with it because the submission size is limited to 50kb.

+ 1 comment It seems there are so many errors in editorial... I doubt if I'm misunderstanding something here:

*"First, we claim that k such numbers can only be obtained if we sort the list and chose k contiguous numbers. This can easily be proved. Suppose we choose numbers X1, X2, X3,....Xr, Xr+1,....,XK (all are in increasing order but not continuous in the sorted list) i.e. there exists a number p which lies between Xr and Xr+1.Now, if we include p and drop X1, our anger coefficient will decrease by an amount = ( \|X1 - X2\| + \|X1 - X3\| + .... + \|X1 - XK\| ) - ( \|p - X2\| + \|p - X3\| + .... + \|p - XK\| ) which is certainly positive. "*Please consider this list:

X1 X2 X3 X4 1 2 3 11

And p is 10 lies between X3 and X4. if you include p and drop X1.

the decrease amount = ( |1 - 2| + |1 - 3| + |1 - 11| ) - ( |10 - 2| + |10 - 3| + |10 - 11|) = 12 - 16 = -4 !

Which is negative!

_"First, we sort the list in increasing order: X1, X2, X3,....XK,XK+1,....,XN. The next step is to find the value of D for the first K elements i.e. from X1 to XK. suppose we have calculated D for first i elements. when we include Xi+1, the value of D increases by ( \|Xi+1 - X1\| + \|Xi+1 - X2\| +....+ \|Xi+1 - Xi\| ), which in turn is equal to ( i*XK - (X1 + X2 + ....+Xi) ). We just need to store the sum of current elements and repeat the step for i = 1 to k-1."_

`( i*XK - (X1 + X2 + ....+Xi) )`

should be`(i * Xi+1 - (X1 + X2 + ....+Xi) )`

??*"New anger coefficient = old anger coefficient + ( \|XK+1 - X2\| + \|XK+1 - X3\| + .... + \|XK+1 - XK\| ) - ( \|X1 - X2\| + \|X1 - X3\| + .... + \|X1 - XK\| ). This can be written in the following form: New anger coefficient = old anger coefficient + K.(XK - X1) - K.(X1 + X2 +....+XK) + ( X1 - XK)"*

How can`Xk+1`

items disappear?

Sort 70 Discussions, By:

Please Login in order to post a comment