Problem: Why Did the Cow Cross the Road
Internal Solution: USACO Platinum 2017 February - Mincross
Official Analysis: Solution for P1 Platinum 2017 February
From the Internal Solution:
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] .
And from the Official Analysis:
Two cows i, j: will cross if (ai<aj) ≠ (bi<bj)
From Both, it states that inversions are what causes crosses which I agree to.
However, I think that there is another case for which a cross would occur:
when \texttt{posA}[i] < \texttt{posA}[j] and \texttt{posB}[i] < \texttt{posB}[j],
but also min(\texttt{posB}[i], \texttt{posB}[j]) > max(\texttt{posA}[i], \texttt{posA}[j]) .
I.e. when i and j in array B is completely on the right of the i and j in array A.
In this case even when there is no inversions, a crossing still happens.
Please Inform me if I am understanding anything wrong.
Any help is really appreciated!!!
Thank you in advance,
Eric Liu