Rotation Matching (Codeforces 1365C)
Tags: Greedy, data structures

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: 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: Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.

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$$$.

Sample Inputs:
5
1 2 3 4 5
2 3 4 5 1

5
5 4 3 2 1
1 2 3 4 5

4
1 3 2 4
4 2 3 1

Sample Outputs:
5

1

2

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pos2 = [0] * (n + 1)
for i in range(n):
    pos2[b[i]] = i
d = [0] * (n + 1)
for i in range(0, n):
    if i >= pos2[a[i]]:
        d[i - pos2[a[i]]] += 1
    else:
        d[n + i - pos2[a[i]]] += 1
print(max(d))

Solution (Python):
n = int(input())
pos = [0] * (n + 1)
for (i, x) in enumerate(map(int, input().split())):
    pos[x] = i
cnt = [0] * n
for (i, x) in enumerate(map(int, input().split())):
    p = pos[x]
    cnt[(p - i) % n] += 1
print(max(cnt))

Solution (Python):
def solve(n, a, b):
    ixs = [None] * (n + 1)
    for (i, v) in enumerate(a):
        ixs[v] = i
    shifts = [0] * n
    for (i, v) in enumerate(b):
        base = i - ixs[v]
        if base < 0:
            base += n
        shifts[base] += 1
    return max(shifts)
n = int(input())
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
print(solve(n, a, b))