Why Did the Cow Cross the Road

Problem Statement

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).

Intuition

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.

Solution

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.

Common Mistakes

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.

Code

My solution can be found here

Written by Robert Chen

Notice any mistakes? Please email us at learn@teamscode.com so that we can fix any inaccuracies.