(Analysis by Benjamin Qi)

Observation: Consider two cows $a_i$ and $a_j$ such that $a_i$ is to the left of $a_j$ in $a$ but to the right of $a_j$ in $b$ (for example, $a_3=3$ and $a_4=2$ in sample 2). Then Farmer John must choose cow $a_j$ at least once.

Proof: If cow $a_i$ is to the left of cow $a_j$, then any modification FJ performs that does not involve choosing cow $a_j$ preserves the relative order of cows $a_i$ and $a_j$. So if FJ never chooses cow $a_j$ then $a_i$ will still be to the left of $a_j$ at the end, contradiction.

Claim: The answer is equal to the number of cows $a_j$ in $a$ such that there exists $a_i$ such that $(a_i,a_j)$ satisfy the observation above. This will be proven later in the analysis.

This claim leads to a solution in $O(N^3)$. Go through all pairs of cows $(a_i,a_j)$ such that $i<j$ and check if cow $j$ must be moved according to the observation above. Then print the total number of cows that need to be moved.

My code:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

need_to_move = [0]*N

def pos_in_B(x):
for i in range(N):
if B[i] == x:
return i

for i in range(N):
for j in range(i+1,N):
if pos_in_B(A[i]) > pos_in_B(A[j]):
need_to_move[j] = 1

print(sum(need_to_move))


One simplification we can make is by relabeling the cows so that cow $b_i$ becomes cow $i$. For example, we may rephrase the second sample case,

a = [5 1 3 2 4] -> a = [2 4 5 3 1]
b = [4 5 2 1 3] -> b = [1 2 3 4 5]


Then we may rephrase the problem as sorting the cows in increasing order of label. Now we can rephrase the observation as checking for each $j$, whether there exists $i<j$ such that $a_i>a_j$. Here is a solution running in $O(N^2)$:

My code:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

pos_in_B = [0]*(N+1)
for i in range(N):
pos_in_B[B[i]] = i+1

A = [pos_in_B[v] for v in A]
# now assume B=1...N

ans = 0
for j in range(N):
need_to_move_j = False
for i in range(j):
if A[i] > A[j]:
need_to_move_j = True
if need_to_move_j:
ans += 1
print(ans)


We can optimize this to $O(N)$ time by maintaining the quantity $\texttt{max_so_far}=\max(a_1,a_2,\ldots,a_{j-1})$. If $\texttt{max_so_far}>a_j$, then we should to move cow $a_j$ to the left while there is a cow with greater label than $a_j$ to the left of cow $a_j$. Otherwise, cow $a_j$ has greater label than all cows to the left of it, and we set $\texttt{max_so_far}=a_j$. In either case, the first $j$ cows in $a$ will be in the same order as they are in $b$. It follows that when $j=N$, $a=b$.

My code:

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

pos_in_B = [0]*(N+1)
for i in range(N):
pos_in_B[B[i]] = i+1

A = [pos_in_B[v] for v in A]
# now assume B=1...N

max_so_far = 0
ans = 0

for a in A:
if a > max_so_far:
max_so_far = a
else:  # max_so_far remains the same
ans += 1

print(ans)


Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class MovingLeft {

public static void main(String[] args) throws IOException {
int[] a = new int[n];
int[] b = new int[n];
for (int j = 0; j < n; j++) {
a[j] = Integer.parseInt(tokenizerA.nextToken());
b[j] = Integer.parseInt(tokenizerB.nextToken());
}
boolean[] moved = new boolean[n + 1];
int k = 0;
for (int j = 0; j < n; j++) {
while (moved[a[k]]) {
k++;
}
if (b[j] == a[k]) {
k++;
} else {