Official Analysis (C++)

Explanation

Let $\texttt{posA}[i]$ denote the position of cow $i$ in array $\texttt{A}$ and $\texttt{posB}[i]$ denote the position of cow $i$ in array $\texttt{B}$ (where arrays $\texttt{A}$ and $\texttt{B}$ represent the two sides of the road). Observe that two cows $i$ and $j$ will cross if $\texttt{posA}[i] < \texttt{posA}[j]$ and $\texttt{posB}[i] > \texttt{posB}[j]$.

We can use the above fact to compute the initial number of crossings. Using an Order Statistics Tree, we can initially store all $\texttt{posB}[\texttt{A}[i]]$. To obtain the number of cows that cross with cow $i$, we can erase all $\texttt{posB}[\texttt{A}[j]]$ such that $j < i$ and query for the number of elements in the tree that are less than $\texttt{posB}[\texttt{A}[i]]$. To optimize erasing, we can loop from $1$ to $N$ and erase each $\texttt{posB}[\texttt{A}[i]]$ before each query.

To handle cyclic shifts, we only care about moving the first cow to the last position. All other crossings will hold constant. Consider shifting array $\texttt{B}$ to the left:

• To detach existing crossings from $\texttt{B}[1]$, we must subtract $\texttt{posA}[\texttt{B}[1]]$ because we know for all positions $j$ such that $j < \texttt{posA}[\texttt{B}[1]]$, $\texttt{A}[j]$ is attached to some position $\texttt{B}[k]$ such that $k > 1$.
• Now, $\texttt{B}[1]$ becomes $\texttt{B}[N]$. The number of new crossings is $N - \texttt{posA}[\texttt{B}[N]]$ because we know for all positions $j$ such that $j > \texttt{posA}[\texttt{B}[N]]$, $\texttt{A}[j]$ is attached to some position $\texttt{B}[k]$ such that $k < N$.

Our answer is the minimum crossings out of all cyclic shifts. Note that we may have to consider shifting $A$ as well.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;