Feb, Problem 1 | Why Did the Cow Cross the Road

### 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 [email protected] so that we can fix any inaccuracies.