*A writeup of Feb number 1 from the USACO platinum problem set*

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