codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1365C.md (2744B)


      1 Source: https://codeforces.com/problemset/problem/1365/C
      2 
      3 C. Rotation Matching
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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$.
     22 
     23 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.
     24 
     25 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:
     26 
     27 * $i = j$, that is, they are at the same index.
     28 * $a_i = b_j$
     29 
     30 His two disciples are allowed to perform the following operation any number of times:
     31 
     32 * choose a number $k$ and cyclically shift one of the permutations to the left or right $k$ times.
     33 
     34 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.
     35 
     36 Help Ishika and Hriday find the maximum number of pairs of elements that match after performing the operation any (possibly zero) number of times.
     37 
     38 Input
     39 
     40 The first line of the input contains a single integer $n$ $(1 \le n \le 2 \cdot 10^5)$ — the size of the arrays.
     41 
     42 The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le n)$ — the elements of the first permutation.
     43 
     44 The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ $(1 \le b_i \le n)$ — the elements of the second permutation.
     45 
     46 Output
     47 
     48 Print the maximum number of matching pairs of elements after performing the above operations some (possibly zero) times.
     49 
     50 Examples
     51 
     52 Input
     53 
     54 ```
     55 5
     56 1 2 3 4 5
     57 2 3 4 5 1
     58 ```
     59 
     60 Output
     61 
     62 ```
     63 5
     64 ```
     65 
     66 Input
     67 
     68 ```
     69 5
     70 5 4 3 2 1
     71 1 2 3 4 5
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 1
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 4
     84 1 3 2 4
     85 4 2 3 1
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 2
     92 ```
     93 
     94 Note
     95 
     96 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\}$.
     97 
     98 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$.
     99 
    100 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$.