We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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:
X1X2X3X412311
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?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Angry Children 2
You are viewing a single comment's thread. Return to all comments →
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:
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?