POJ 1990 MooFest Report

View this problem on POJ: 1990 MooFest.

Here is my resolution:

First, sort cows by v value.

Then, for each cow in ascend order,

calculate  DS : the sum of the differences of distances between this cow and each of the dealted cows. The answer is $$\sum_i{DS_i v_i}$$

How to calculate DS? Use Tree-Structure Array.

Tree-Structure Array may be used to

• store the number of cows that has a smaller $$x$$ value as $$N_i$$ for the $$i$$-th cow.
• store the sum of $$x$$ values which is smaller than the $$x$$ value of the current cow as $$S_i$$ for the $$i$$-th cow.

The sum of all $$x$$ values when dealing the $$i$$-th cow can be calculated, which we denote as $$T_i$$.

Then $$DS_i = (x_i N_i - S_i) + [(T_i - S_i) - (i - 1 - N_i) x_i]$$

The sort costs $$O(n log(n))$$ (if you use quick sort), or $$O(n)$$ (if you use radix sort).

For each cow, we need $$O(log(n))$$ to calculate the DS(i), this is decided by the algorithm of Tree-Structure Array.

So, the total complexity of this algorithm is $$O(n log(n))$$.1

1. For this problem, the answer may exceed the scope of 32-bit integer , so you may use int64 or long long in C++ language, or BigInteger in Java.