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.
I looked at my submitted code and found that I did the optimal strategy in O(N) after the O(N*log(N)) sorting but the value of the objective function lazily in O(N^2) to make the code short. I believe I can do the objective function in O(N) after sorting as well, because
S=sum_{i,j=1..N} |A[i]-A[j]|
can be calculated in O(N) after sorting using the partial sum trick (beware of overflow). One may then apply this method three times to all numbers to get S, the numbers given to Li to get S1, and the numbers given to Lu to get S2. Then (S-S1-S2)/2 should give the answer.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Fair Cut
You are viewing a single comment's thread. Return to all comments →
I looked at my submitted code and found that I did the optimal strategy in O(N) after the O(N*log(N)) sorting but the value of the objective function lazily in O(N^2) to make the code short. I believe I can do the objective function in O(N) after sorting as well, because
S=sum_{i,j=1..N} |A[i]-A[j]|
can be calculated in O(N) after sorting using the partial sum trick (beware of overflow). One may then apply this method three times to all numbers to get S, the numbers given to Li to get S1, and the numbers given to Lu to get S2. Then (S-S1-S2)/2 should give the answer.