1269B.md (2224B)
1 Source: https://codeforces.com/problemset/problem/1269/B 2 3 B. Modulo Equality 4 5 time limit per test 6 7 3 seconds 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 You are given a positive integer $m$ and two integer sequence: $a=[a_1, a_2, \ldots, a_n]$ and $b=[b_1, b_2, \ldots, b_n]$. Both of these sequence have a length $n$. 22 23 Permutation is a sequence of $n$ different positive integers from $1$ to $n$. For example, these sequences are permutations: $[1]$, $[1,2]$, $[2,1]$, $[6,7,3,4,1,2,5]$. These are not: $[0]$, $[1,1]$, $[2,3]$. 24 25 You need to find the non-negative integer $x$, and increase all elements of $a_i$ by $x$, modulo $m$ (i.e. you want to change $a_i$ to $(a_i + x) \bmod m$), so it would be possible to rearrange elements of $a$ to make it equal $b$, among them you need to find the smallest possible $x$. 26 27 In other words, you need to find the smallest non-negative integer $x$, for which it is possible to find some permutation $p=[p_1, p_2, \ldots, p_n]$, such that for all $1 \leq i \leq n$, $(a_i + x) \bmod m = b_{p_i}$, where $y \bmod m$ — remainder of division of $y$ by $m$. 28 29 For example, if $m=3$, $a = [0, 0, 2, 1], b = [2, 0, 1, 1]$, you can choose $x=1$, and $a$ will be equal to $[1, 1, 0, 2]$ and you can rearrange it to make it equal $[2, 0, 1, 1]$, which is equal to $b$. 30 31 Input 32 33 The first line contains two integers $n,m$ ($1 \leq n \leq 2000, 1 \leq m \leq 10^9$): number of elemens in arrays and $m$. 34 35 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt m$). 36 37 The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \lt m$). 38 39 It is guaranteed that there exists some non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$. 40 41 Output 42 43 Print one integer, the smallest non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$ for all $1 \leq i \leq n$. 44 45 Examples 46 47 Input 48 49 ``` 50 4 3 51 0 0 2 1 52 2 0 1 1 53 ``` 54 55 Output 56 57 ``` 58 1 59 ``` 60 61 Input 62 63 ``` 64 3 2 65 0 0 0 66 1 1 1 67 ``` 68 69 Output 70 71 ``` 72 1 73 ``` 74 75 Input 76 77 ``` 78 5 10 79 0 0 0 1 2 80 2 1 0 0 0 81 ``` 82 83 Output 84 85 ``` 86 0 87 ```