Rotation Matching
Contest: Codeforces Round 648 (Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, data structures, greedy, implementation

After the mysterious disappearance of Ashish, his two favourite disciples Ishika and Hriday, were each left with one half of a secret message. These messages can each be represented by a permutation of size $$$n$$$. Let's call them $$$a$$$ and $$$b$$$.

Note that a permutation of $$$n$$$ elements is a sequence of numbers $$$a_1, a_2, \ldots, a_n$$$, in which every number from $$$1$$$ to $$$n$$$ appears exactly once.

The message can be decoded by an arrangement of sequence $$$a$$$ and $$$b$$$, such that the number of matching pairs of elements between them is maximum. A pair of elements $$$a_i$$$ and $$$b_j$$$ is said to match if:

- $$$i = j$$$, that is, they are at the same index.
- $$$a_i = b_j$$$

His two disciples are allowed to perform the following operation any number of times:

- choose a number $$$k$$$ and cyclically shift one of the permutations to the left or right $$$k$$$ times.

A single cyclic shift to the left on any permutation $$$c$$$ is an operation that sets $$$c_1:=c_2, c_2:=c_3, \ldots, c_n:=c_1$$$ simultaneously. Likewise, a single cyclic shift to the right on any permutation $$$c$$$ is an operation that sets $$$c_1:=c_n, c_2:=c_1, \ldots, c_n:=c_{n-1}$$$ simultaneously.

Help Ishika and Hriday find the maximum number of pairs of elements that match after performing the operation any (possibly zero) number of times.

Input format:
The first line of the input contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the size of the arrays.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le n)$$$ — the elements of the first permutation.

The third line contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ $$$(1 \le b_i \le n)$$$ — the elements of the second permutation.

Output format:
Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first case: $$$b$$$ can be shifted to the right by $$$k = 1$$$. The resulting permutations will be $$$\{1, 2, 3, 4, 5\}$$$ and $$$\{1, 2, 3, 4, 5\}$$$.

For the second case: The operation is not required. For all possible rotations of $$$a$$$ and $$$b$$$, the number of matching pairs won't exceed $$$1$$$.

For the third case: $$$b$$$ can be shifted to the left by $$$k = 1$$$. The resulting permutations will be $$$\{1, 3, 2, 4\}$$$ and $$$\{2, 3, 1, 4\}$$$. Positions $$$2$$$ and $$$4$$$ have matching pairs of elements. For all possible rotations of $$$a$$$ and $$$b$$$, the number of matching pairs won't exceed $$$2$$$.

Example input:
5
1 2 3 4 5
2 3 4 5 1

Example output:
5

Example input:
5
5 4 3 2 1
1 2 3 4 5

Example output:
1

Editorial:
Key Idea:
We only need to perform shifts on one of the arrays. Moreover, all the shifts can be of the same type (right or left)!
Solution:
First of all, a left cyclic shift is the same as $$$n - 1$$$ right cyclic shifts and vice versa. So we only need to perform shifts of one type, say right.
Moreover, a right cyclic shift of $$$b$$$ is the same as performing a left cyclic shift on $$$a$$$ and vice versa. So we don't need to perform any shifts on $$$b$$$.
Now the problem reduces to finding the maximum number of matching pairs over all right cyclic shifts of $$$a$$$. Since $$$n$$$ right cyclic shifts on $$$a$$$ results in $$$a$$$ again, there are only $$$n - 1$$$ right cyclic shifts possible.
Since both arrays are a permutation, each element in $$$a$$$ would match with its corresponding equal element in $$$b$$$ only for one of the shifts. For example, if $$$a$$$ is $$$\{{2, 3, 1\}}$$$ and $$$b$$$ is $$$\{{3, 1, 2\}}$$$, the number $$$3$$$ in $$$a$$$ would match with the number $$$3$$$ in $$$b$$$ only if one right cyclic shift is performed. So for each element in $$$a$$$ we can find the number of right cyclic shifts after which it would match with its corresponding equal element in $$$b$$$. If $$$a_i$$$ = $$$b_j$$$, then $$$a_i$$$ would match with $$$b_j$$$ after $$$k = j - i$$$ right cyclic shifts. If $$$j - i \lt 0$$$, then $$$a_i$$$ would with $$$b_j$$$ after $$$n - j + i$$$ shifts.
Now for each shift, we can find the number of matching pairs and take the maximum.
Time complexity: $$$O(n)$$$ or $$$O(n \cdot log(n))$$$ if you use a map.