USACO 2025 January Contest, Silver
Problem 1. Cow Checkups
Contest has ended.
Log in to allow submissions in analysis mode
Farmer John's $N$ ($1 \leq N \leq 5 \cdot 10^5$) 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 \leq a_i \leq 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 species $b_i$ ($1 \leq b_i \leq 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 \leq l \le r \leq 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. Find the sum of the number of cows that are checked by the veterinarian over all $N(N+1)/2$ possible operations.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains an integer $N$.The second line contains $a_1, a_2, \ldots, a_N$.
The third line contains $b_1, b_2, \ldots, b_N$.
OUTPUT FORMAT (print output to the terminal / stdout):
Output one line with the sum of the number of cows that are checked by the veterinarian over all possible operations.SAMPLE INPUT:
3 1 3 2 3 2 1
SAMPLE OUTPUT:
3
If FJ chooses ($l=1,r=1$), ($l=2,r=2$), or ($l=3,r=3$) then no cows will be checked. Note that those operations do not modify the location of the cows.
The following operations result in one cow being checked.
- $l=1,r=2$: FJ reverses the order of the first and second cows so the species of each cow in the new lineup will be $[3,1,2]$. The first cow will be checked.
- $l=2,r=3$: FJ reverses the order of the second and third cows so the species of each cow in the new lineup will be $[1,2,3]$. The second cow will be checked.
- $l=1,r=3$: FJ reverses the order of the first, second, and third cows so the species of each cow in the new lineup will be $[2,3,1]$. The third cow will be checked.
The total number of cows checked over all six operations is $0+0+0+1+1+1=3$.
SAMPLE INPUT:
3 1 2 3 1 2 3
SAMPLE OUTPUT:
12
There are three possible operations that cause $3$ cows to be checked: ($l=1,r=1$), ($l=2,r=2$), and ($l=3,r=3$). The remaining operations each result in $1$ cow being checked. The total number of cows checked over all six operations is $3+3+3+1+1+1=12$.
SAMPLE INPUT:
7 1 3 2 2 1 3 2 3 2 2 1 2 3 1
SAMPLE OUTPUT:
60
SCORING:
- Input 4: $N\le 100$
- Input 5: $N\le 5000$
- Inputs 6-9: $a_i, b_i$ are all generated uniformly at random in the range $[1,N]$
- Inputs 10-15: $a_i, b_i$ are all generated uniformly at random in the range $[1,2]$
- Inputs 16-23: No additional constraints.
Problem credits: Chongtian Ma, Haokai Ma, and Alex Liang