You are viewing a single comment's thread. Return to all 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.
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 →
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.
First, we need to find angry coefficient for first K items. This can be done in O(K)
Now, we need to find the anger coefficient from k+1th term till last term.
The rest if figuring out the code.