INTEG @user-rsaha solution to this problem

general
1

I could not understand the 3rd step … :(…Can somebody please explain??

http://discuss.codechef.com/questions/23733/integ-editorial

2

Let the SORTED ARRAY OF NEGATIVE INTEGERS be ARR[-a1,-a2,-a3,…,an] ,where (-a1<-a2<-a3<…<-an)

Take an Example:

Let X=2 , BE THE COST OF FIRST TYPE OPERATION…

Now, You have to keep increasing the Array Elements and stop as soon as -a3 becomes ZERO… (INCREASING THE ARRAY ELEMENTS BEYOND THIS WILL NOT BENIFIT YOU.!!)
… ALSO , NOTE : When -a3 becomes ZERO , all the successive NEGATIVE INTEGERS after -a3 also becomes >= ZERO … This is the main Step …

Hence -> Cost for FIRST type operation -> c1 = 2*a3;

Now You Also have to make the remaining -ve Integers >= 0

->SUM OF LEFTOVER -ve ELEMENTS = -a1-a2+(2*a3) … (Since both -a1 & -a2 is increased a3 times now :slight_smile: … )

Hence -> Cost of SECOND type operation -> c2 = a1 + a2 - 2*a3 … (to make the LEFTOVER -ve ELEMENTS = ZERO)

->TOTAL COST = (c1+c2) = 2a3 + a1+a2-2a3 = a1+a2 … (ie : SUM OF THE LAST Xth ELEMENT if you make them +ve while Inserting !!)

Hope it helped !

4 Likes
3

thanks :)…