1
$\begingroup$

Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from list $B$ such that $a>b$.

More precisely, define $$ Q(A,B) = \sum_{i,j} \text{sign}(a_i-b_j)$$ If $Q(A,B) = 0$, then we can say the lists "tie". If $Q(A,B)>0$ then $A$ "beats" $B$, and likewise $Q(A,B)<0$ can be said as $A$ "loses" to $B$.

The naive way of calculating this comparison of lists involves checking each pair of elements and thus takes $n^2$ time.

Is there a faster way to calculate this?

Note, that somewhat non-intuitively, $A$ can still beat $B$ even if the average value of $A$ is less than $B$. (Also, even more non-intuitive, this comparison operator is non-transitive. Known as "intransitive dice", you can have dice such that A beats B, B beats C, C beats A.)

I believe if we take the $O(n \log n)$ hit to sort $A$ and $B$ first, then there should be a better way to calculate the comparison. But I'm having trouble filling in the pieces. Hopefully this is a useful hint instead of a red-herring.

$\endgroup$
1
$\begingroup$

Let $A \cup B$ denote the union of $A$ and $B$. Sort $A \cup B$ into increasing order, keeping track for each element which list it came from. Now for each element of this sorted list, annotate it with the number of elements of $A$ that are smaller than it and the number of elements of $B$ that are smaller than it. Those annotations can be filled in with a single linear scan (starting from the start of the list, and scanning left-to-right, and keeping track of the number of elements of $A$ and $B$ seen so far). Then you can compute the sum from those annotations: for each $i$, you can compute $\sum_j \text{sign}(a_i-b_j)$ directly from the annotation.

This algorithm takes $O(n \log n)$ time: $O(n \log n)$ time to sort, plus $O(n)$ for the scan, plus $O(n)$ time to add up the sums.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.