Codeforces Round 648 (Div. 2) |
---|
Закончено |
После мистического исчезнования Ashish, каждый из его любимых учеников Ishika и Hriday, получил одну половину секретного сообщения. Эти сообщения могут быть описаны перестановками размера $$$n$$$. Назовем их $$$a$$$ и $$$b$$$.
Напомним, что перестановка из $$$n$$$ элементов это последовательность чисел $$$a_1, a_2, \ldots, a_n$$$, в которой каждое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.
Сообщение может быть расшифровано из конфигурации перестановок $$$a$$$ и $$$b$$$, в котором количество совпадающих пар элементов максимально. Пара элементов $$$a_i$$$ и $$$b_j$$$ называется совпадающей, если:
Его ученикам разрешается совершать следующую операцию произвольное число раз:
Циклический сдвиг перестановки $$$c$$$ влево это операция, которая присваивает $$$c_1:=c_2, c_2:=c_3, \ldots, c_n:=c_1$$$ одновременно. Аналогично, циклический сдвиг перестановки $$$c$$$ вправо это операция, которая присваивает $$$c_1:=c_n, c_2:=c_1, \ldots, c_n:=c_{n-1}$$$ одновременно.
Помогите Ishika и Hriday найти наибольшее возможное число совпадающих пар в данных перестановках после применения описанных операций несколько (возможно, ноль) раз.
В первой строке записано одно целое число $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — размеры массивов.
Во второй строке записаны $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(1 \le a_i \le n)$$$ — элементы первой перестановки.
В третьей строке записаны $$$n$$$ целых чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ $$$(1 \le b_i \le n)$$$ — элементы второй перестановки.
Выведите наибольшее возможное число совпадающих пар в данных перестановках после применения описанных операций несколько (возможно, ноль) раз.
5 1 2 3 4 5 2 3 4 5 1
5
5 5 4 3 2 1 1 2 3 4 5
1
4 1 3 2 4 4 2 3 1
2
В первом примере можно сдвинуть $$$b$$$ направо на $$$k = 1$$$. Получившиеся перестановки будут $$$\{1, 2, 3, 4, 5\}$$$ и $$$\{1, 2, 3, 4, 5\}$$$.
Во втором примере не требуется совершать никаких операций. По всем возможным сдвигам $$$a$$$ и $$$b$$$, число совпадающих пар не будет превышать $$$1$$$.
В третьем примере можно сдвинуть $$$b$$$ влево на $$$k = 1$$$. Получившиеся перестановки будут $$$\{1, 3, 2, 4\}$$$ и $$$\{2, 3, 1, 4\}$$$. Позиции $$$2$$$ и $$$4$$$ будут являться совпадающей парой. По всем возможным циклическим сдвигам $$$a$$$ и $$$b$$$, количество совпадающих пар не будет превышать $$$2$$$.
Название |
---|