Given a set of cows on each side of the road, assuming we can rotate either side, find the minimum number of crossing pairs.
We define a pair of cows as crossing if
(A_i < A_j) != (B_i < B_j).
Assume that we rotate only the left side. When we rotate the last cow to the top, we remove exactly
N - 1 - B_i crossings and create exactly
B_i new ones. That’s because we know that the cow
i crosses every cow below
B_i right now, and will cross every cow above
B_i once we move it to the top.
Thus, we iterate through N such rotations, keeping track of a running minimum. The number of crossing paths for an initial setup is a well-known problem, and can be solved with a BIT.
It’s important to remember to rotate both sides. Rotating one side alone does not guarantee getting the minimum. This bug caused me a lot of headaches.
My solution can be found here
Written by Robert Chen
Notice any mistakes? Please email us at [email protected] so that we can fix any inaccuracies.