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.io.InputStreamReader; import java.util.StringTokenizer; public class MovingLeft { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); StringTokenizer tokenizerA = new StringTokenizer(in.readLine()); StringTokenizer tokenizerB = new StringTokenizer(in.readLine()); 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()); } int answer = 0; 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 { answer++; moved[b[j]] = true; } } System.out.println(answer); } }