Description

There are $N$ students in a class. Each student is assigned a number from $0$ to $N - 1$ according to their current class ranking. That is, student $i$ (for all $0 \le i \le N - 1$) currently has class rank $i$. Here rank $0$ is the best while rank $N-1$ is the worst.

Examinations for English and Mathematics were recently held. Student $i$ (for all $0 \le i \le N - 1$) ranked $A[i]$ in English and $B[i]$ in Mathematics. $A$ and $B$ are permutations of length $N$.

What is a permutation of length $N$? In this problem, a permutation $P$ of length $N$ is an array of length $N$ such that $0 \leq P[i] \leq N-1$ for all $0 \leq i \leq N-1$ and $P[i] \neq P[j]$ for all $0 \leq i < j \leq N-1$. For example, $[2,1,0]$ is a permutation of length $3$, but $[1,2,3]$ and $[2,0,2]$ are not permutations of length $3$.

The teacher would like to rerank the students. The new rank can be represented by a permutation $P$.

For each student $i$, the new class ranking has to satisfy at least one of the following conditions:

• For all $j$ such that $P[j] < P[i]$, student $j$ is better than student $i$ in English ($A[j] < A[i]$), OR
• For all $j$ such that $P[j] < P[i]$, student $j$ is better than student $i$ in Mathematics ($B[j] < B[i]$).

Warning The condition only applies to $j$ such that $P[j] < P[i]$. There is no constraint for those $j$ such that $P[j] \geq P[i]$. For each student $i$, in evaluating whether the condition is satisfied, they must first pick a subject and evaluate said subject against students $j$. The subject where $j$ is better than student $i$ must be the same for different $j$, given the same $i$. You cannot switch subjects while evaluating the condition for student $i$.

The dissatisfaction of the new class ranking is defined as the largest fall in ranking among all students. In other words, the dissatisfaction is the maximum value of $P[i] - i$ (for all $0 \leq i \leq N - 1$).

Warning The dissatisfaction is the maximum value of $P[i] - i$, the values of $i - P[i]$ do not affect the dissatisfaction.

Find the minimum possible dissatisfaction of the new class ranking.

Implementation Details

You should implement the following procedure.

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)

• $N$: the number of students.
• $A$: an array of length $N$ describing the ranking of the English examination.
• $B$: an array of length $N$ describing the ranking of the Mathematics examination.
• This procedure should return the minimum dissatisfaction of the new class ranking.
• This procedure is called exactly once.

Constraints

• $1 \leq N \leq 5\;000\;000$.
• $0 \leq A[i], B[i] \leq N - 1$, for all $0 \leq i \leq N - 1$.
• $A[i] \neq A[j]$, for all $0 \leq i < j \leq N - 1$.
• $B[i] \neq B[j]$, for all $0 \leq i < j \leq N - 1$.

Subtasks

1. (3 points) $N \leq 8$.
2. (4 points) $N \leq 20$.
3. (13 points) $N \leq 500$.
4. (12 points) $N \leq 3000$, $A[i] + B[i] = N - 1$ for all $0 \leq i \leq N - 1$.
5. (19 points) $N \leq 3000$.
6. (15 points) $N \leq 100\;000, A[i] + B[i] = N - 1$ for all $0 \leq i \leq N - 1$.
7. (17 points) $N \leq 100\;000$.
8. (17 points) No additional constraints.

Note: for subtask 8, the grader alone is guaranteed to consume 1500ms of the 3000ms time limit.

Example

Consider the following call.

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

In this example, one way to assign the new ranking is $P = [0, 2, 3, 4, 1]$.

Consider student $1$ with $P[1] = 2$. All students $j$ with $P[j] < P[1]$ have a better Mathematics rank than student $1$, so this student satisfies the class ranking condition.

Next, consider student $2$ with $P[2] = 3$. All students $j$ with $P[j] < P[2]$ have a better English rank than student $2$, so this student also satisfies the class ranking condition.

It can be checked for all other students that they also satisfy the class ranking condition.

The dissatisfaction of the new ranking is $1$. There is no other new ranking with lower dissatisfaction, so the procedure should return $1$.

Sample Grader

Input format:

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

Output format:

An integer representing the return value of minimum_dissatisfaction.