問題一覧 > 通常問題

No.1922 Separate and Attach

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 24
作問者 : 0214sh7
お気に入りにしたユーザー ProblemId : 8084 / 自分の提出
問題文最終更新日: 2022-05-01 23:54:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given permutations $P, Q$ of $1, 2, \dots, N$. You can perform the following operation on the permutation $P$.

Operation
  • Choose any (not necessarily contiguous) subsequence of $P$ and call it $S$.
  • Let $T$ be the concatenation, in the order in $P$, of the elements of $P$ not contained in $S$.
  • Replace $P$ with the concatenation of $S,T$ in this order.

You want to make $P$ equal to $Q$ by repeating this operation some number of times. What is the minimum number of operations required? It can be proved that $P$ can be made equal to $Q$ with a finite number of operations.

Input

The input is given from standard input in the following format.

$N$
$P_1$ $P_2$ $\cdots$ $P_N$ 
$Q_1$ $Q_2$ $\cdots$ $Q_N$
  • $1 \le N \le 10^5$
  • $P,Q$ are permutations of length $N$
  • All inputs are integers

Output

Output the answer.

Sample

Sample 1
Input
4
3 4 2 1
2 4 1 3
Output
2

The following $2$ operations make $(3,4,2,1)$ equal to $(2,4,1,3)$.

  • Take the subsequence $(4,1)$ from $P$ and concatenate it with the remaining $(3,2)$. $P=(4,1,3,2)$ results.
  • Take the subsequence $(2)$ from $P$ and concatenate it with the remaining $(4,1,3)$. $P=(2,4,1,3)$ results.

$P$ cannot be made equal to $Q$ with $1$ operation, so output $2$.

Sample 2
Input
5
1 2 3 4 5
1 2 3 4 5
Output
0

$P$ and $Q$ may be equal from the beginning.

Sample 3
Input
15
4 6 8 9 15 7 12 2 1 11 10 14 5 3 13 
10 11 12 3 6 4 7 14 1 2 5 15 9 13 8
Output
4

Source

CPCTF22

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。