USACO 2022 February Contest, Bronze Problem 2. Photoshoot 2

USACO 2022 February Contest, Bronze Problem 2. Photoshoot 2

In what seems to be a familiar occurrence, Farmer John is lining up his NN cows (1N1051≤N≤105), conveniently numbered 1N1…N, for a photograph.

Initially, the cows are lined up in the order a1,a2,,aNa1,a2,…,aN from left to right. Farmer John's goal is to line up the cows in the order b1,,bNb1,…,bN from left to right. To accomplish this, he may perform a series of modifications to the ordering. Each modification consists of choosing a single cow and moving it some number of positions to the left.

Please count the minimum number of modifications required in order for Farmer John to line up his cows in the desired order.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains NN. The second line contains a1,a2,,aNa1,a2,…,aN. The third line contains b1,b2,,bNb1,b2,…,bN.

OUTPUT FORMAT (print output to the terminal / stdout):

Print the minimum number of modifications required to produce Farmer John's desired ordering.

SAMPLE INPUT:

5
1 2 3 4 5
1 2 3 4 5

SAMPLE OUTPUT:

0

In this example, the cows are already in the desired order, so no modifications are required.

SAMPLE INPUT:

5
5 1 3 2 4
4 5 2 1 3

SAMPLE OUTPUT:

2

In this example, two modifications suffice. Here is one way Farmer John can rearrange his cows:

  1. Choose cow 44 and move it four positions to the left.
  2. Choose cow 22 and move it two positions to the left.

   5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3

SCORING:

 

  • Test cases 3-6 satisfy N100N≤100.
  • Test cases 7-10 satisfy N5000N≤5000.
  • Test cases 11-14 satisfy no additional constraints.

 

Problem credits: Benjamin Qi

USACO 2022 February Contest, Bronze Problem 2. Photoshoot 2 题解(翰林国际教育提供,仅供参考)

题解请注册登录查看

[/hide]

(Analysis by Benjamin Qi)

Observation: Consider two cows aiai and ajaj such that aiai is to the left of ajaj in aa but to the right of ajaj in bb (for example, a3=3a3=3 and a4=2a4=2 in sample 2). Then Farmer John must choose cow ajaj at least once.

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

Claim: The answer is equal to the number of cows ajaj in aa such that there exists aiai such that (ai,aj)(ai,aj) satisfy the observation above. This will be proven later in the analysis.

This claim leads to a solution in O(N3)O(N3). Go through all pairs of cows (ai,aj)(ai,aj) such that i<ji<j and check if cow jj 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 bibi becomes cow ii. 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 jj, whether there exists i<ji<j such that ai>ajai>aj. Here is a solution running in O(N2)O(N2):

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)O(N) time by maintaining the quantity max_so_far=max(a1,a2,,aj1)max_so_far=max(a1,a2,…,aj−1). If max_so_far>ajmax_so_far>aj, then we should to move cow ajaj to the left while there is a cow with greater label than ajaj to the left of cow ajaj. Otherwise, cow ajaj has greater label than all cows to the left of it, and we set max_so_far=ajmax_so_far=aj. In either case, the first jj cows in aa will be in the same order as they are in bb. It follows that when j=Nj=Na=ba=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);
    }
}

[/hide]

翰林国际教育资讯二维码