2025 January USACO Bronze Problems/Problem 3
Contents
Problem
Note
Note: We suggest using a language other than Python to earn full credit on this problem.
Problem
Farmer John's N (1≤N≤7500) cows are standing in a line, with cow 1 at the front of the line and cow N at the back of the line. FJ's cows also come in many different species. He denotes each species with an integer from 1 to N. The i'th cow from the front of the line is of species a_i (1≤a_i≤N).
FJ is taking his cows to a checkup at a local bovine hospital. However, the bovine veterinarian is very picky and wants to perform a checkup on the i'th cow in the line, only if it is of species b_i (1≤b_i≤N).
FJ is lazy and does not want to completely reorder his cows. He will perform the following operation exactly once.
- Select two integers l and r such that 1≤l≤r≤N. Reverse the order of the cows that are between the l-th cow and the r-th cow in the line, inclusive.
FJ wants to measure how effective this approach is. For each c=0…N, help FJ find the number of distinct operations (l,r) that result in exactly c cows being checked. Two operations (l_1,r_1) and (l_2,r_2) are different if l_1≠l_2 or r_1≠r_2.
Input Format
The first line contains an integer N.
The second line contains a_1,a_2,…,a_N.
The third line contains b_1,b_2,…,b_N.
Output Format
Output N+1 lines with the i-th line containing the number of distinct operations (l,r) that result in i−1 cows being checked.
Sample Input
3 1 3 2 3 2 1
Sample Output
3 3 0 0
Scoring
Inputs 4-6: N≤100
Inputs 7-13: No additional constraints.
Solution
First, let's calculate the number of indices i where a_i is already equal to b_i. Let's denote this number as S. Note that if we are not reversing a subarray that contains i, this index will always contribute to the number of total checkups.
We can visualize reversing an array as a series of swaps. Suppose we want to reverse an array b of length M, then it is equivalent to swapping b_i with b_(M−i+1) over all 1≤i≤⌊M^2⌋.
Suppose we reverse an odd length subarray of length M. Let K represent the index of the middle element of the subarray. We are essentially swapping the (K−1)'th element with the (K+1)'th element, (K−2)'th element with the (K+2) 'th element, …, (K−(M−1)/2)'th element with the (K+(M−1)/2)'th element.
This motivates a solution where we enumerate over K, enumerate over i where we swap the (K−i)'th element with the (K+i)'th element of a, then determine whether a_(K−i)=b_(K−i) or a_(K+i)=b_(K+i). However, it may be the case that the elements that we swapped are already equal to their corresponding elements in b, and after the swap, they are no longer equal. Let x denote the number of integers j among {K−i,K+i} that such that a_j=b_j after the swap, and y denote the number of integers j among the set such that a_j=b_j before the swap. We must add x to S to account for the new cows that can be checked up, and subtract y from S to account for the old cows that cannot be checked up. This way, we are always able to keep track of the total number of cows that can be checked up when enumerating.
Even-length subarrays can be enumerated similarly. The only difference is that the middle element is technically between the M/2'th and the (M/2+1)'th element. Let K represent the index to the left of the middle of the subarray, then we are swapping the (K−i+1)'th element with the (K+i)'th element for each i. We can track the total number of checked cows in the same way as odd-length subarrays.
Enumerating over all K and i over all subarrays requires O(N^2) time.
