Свапы как ориентация графа на значениях — задача «Два массива» РАЗБОР

Источник задачи: региональный этап Олимпиады им. М.В. Келдыша, 2025, задача F.

Что дано

Даны два массива $a = (a_1, \ldots, a_n)$ и $b = (b_1, \ldots, b_n)$ одинаковой длины $n$; все значения массивов — целые числа от $1$ до $2n$ включительно. Разрешено выполнить произвольное число операций следующего вида: выбрать индекс $i \in \{1, \ldots, n\}$ и поменять местами значения $a_i$ и $b_i$.

Обозначим $f(c)$ — количество различных значений в массиве $c$. Задача — максимизировать сумму $f(a) + f(b)$ после произвольного числа таких операций и выдать сами массивы $a$ и $b$, на которых максимум достигается.

Ограничения

• $1 \leq n \leq 10^5$
• $1 \leq a_i, b_i \leq 2n$

Формат ввода

Первая строка — одно число $n$. Вторая строка — $n$ чисел $a_1, a_2, \ldots, a_n$ через пробел. Третья строка — $n$ чисел $b_1, b_2, \ldots, b_n$ через пробел.

Формат вывода

Первая строка — одно число, максимальное значение $f(a) + f(b)$. Вторая строка — итоговый массив $a$ (через пробел). Третья строка — итоговый массив $b$ (через пробел).

Пример 1 руками

n = 5
a = [1, 2, 4, 4, 4]
b = [1, 3, 3, 5, 2]

Пары: $(1,1), (2,3), (4,3), (4,5), (4,2)$.

Операции — три свапа в позициях 2, 4 и 5:

После свапа $i=2$: $a_2 \leftrightarrow b_2$ → $a = [1, 3, 4, 4, 4]$, $b = [1, 2, 3, 5, 2]$.

После свапа $i=4$: $a_4 \leftrightarrow b_4$ → $a = [1, 3, 4, 5, 4]$, $b = [1, 2, 3, 4, 2]$.

После свапа $i=5$: $a_5 \leftrightarrow b_5$ → $a = [1, 3, 4, 5, 2]$, $b = [1, 2, 3, 4, 4]$.

$f(a) = 5$ (все разные), $f(b) = 4$ (повторы: четвёрка). Сумма = 9. ✓

---

Идея решения

Граф на значениях

Построим граф на значениях, которые встречаются в массивах. Для каждого индекса $i$ добавим ребро между вершинами $a_i$ и $b_i$ (значения могут быть одинаковыми — тогда получаем петлю). Операцию свапа в позиции $i$ удобно интерпретировать как выбор ориентации этого ребра: если $i$-е ребро ориентировано $u \to v$, то после всех операций $a_i = u$ и $b_i = v$.

Задача: ориентировать все $n$ рёбер так, чтобы максимизировать число вершин, из которых исходит хотя бы одно ребро (вклад в $f(a)$), плюс число вершин, в которые входит хотя бы одно ребро (вклад в $f(b)$).

Переформулирование для ясности:

• Вершины графа — различные значения в объединении $a$ и $b$.
• Рёбра — $n$ рёбер, по одному на каждый индекс $i$.
• Ориентация ребра $\{u, v\}$ как $u \to v$ означает «после операций $a_i = u, b_i = v$».
• $f(a) = |\{v : \text{существует исходящее ребро из } v\}|$ (вклад в $a$).
• $f(b) = |\{v : \text{существует входящее ребро в } v\}|$ (вклад в $b$).

Цель — ориентировать все рёбра так, чтобы максимизировать $f(a) + f(b)$ = «число вершин с исходящим» + «число вершин с входящим».

Вклад вершины

Для каждой вершины $v$:

• Если у $v$ есть и входящее, и исходящее ребро после ориентации — вклад $2$.
• Если только исходящее (или только входящее) — вклад $1$.
• Изолированная — вклад $0$, но изолированных быть не может (каждая вершина появилась из-за хотя бы одного ребра).

Верхняя оценка: если $\text{deg}(v) \geq 2$, можно сделать и входящее, и исходящее — вклад $2$. Если $\text{deg}(v) = 1$ — только одно, вклад $1$.

Но так ли просто? Нет: ориентация глобальна. Если у одной вершины хочется обе — какой-то соседний узел теряет.

Циклы и пути

Если каждое значение встречается $\leq 2$ раз (подгруппа 4), то граф — объединение путей и циклов (каждая вершина степени $\leq 2$).

• Цикл. Ориентируем все рёбра «по часовой»: у каждой вершины ровно одно входящее и одно исходящее. Вклад каждой вершины — $2$.
• Путь $v_1 - v_2 - \ldots - v_k$. Ориентируем от начала к концу: $v_1 \to v_2 \to \ldots \to v_k$. У $v_1$ только исходящее (вклад $1$), у $v_k$ — только входящее (вклад $1$), у внутренних по $2$.

Это подгруппа 4 (15 баллов).

Общий случай

Если некоторые значения встречаются $\geq 3$ раз, граф имеет вершины степени $\geq 3$ — сложнее. Официальное решение делает так:

1. Для каждого значения $x$, встречающегося $\text{cnt}_x$ раз, создаём $\lceil \text{cnt}_x / 2 \rceil$ «клонов» этой вершины (это важный трюк).
2. Получается граф, где у каждой вершины степень $\leq 2$ — то есть снова объединение путей и циклов.
3. Применяем ориентацию по схеме «циклы полностью, путь от начала к концу».
4. Ответ — сумма по всем значениям $\min(\text{cnt}_x, 2)$.

Сложность: $O(n)$.

Сложности вариантов

В этой статье — код на $2^n$ (подгруппа 1) и идея полного решения.

---

Решение: псевдокод (для малых $n$)

читать n, a[], b[]
ответ = 0
для mask = 0..(2^n - 1):
    строим A, B из (a, b) с применением свапа для битов маски
    cur = f(A) + f(B)
    если cur > ответ:
        ответ = cur
        save A, B

вывести ответ, A, B

---

Код решения (подгруппа 1)

Работает для $n \leq 18$ — $2^{18} \cdot 18 \approx 4.7 \cdot 10^6$ операций.

---

Проверим на примерах

Пример 1

$n = 5$, $a = [1, 2, 4, 4, 4]$, $b = [1, 3, 3, 5, 2]$.

Перебор маски $2^5 = 32$. Лучшее — $\text{mask} = 0b10110$: свапаем позиции 1, 2, 4 (0-based). $A = [1, 3, 4, 5, 4]$... подожди, проверю: свап $i=1$: $(a_1, b_1) = (2, 3) \to (3, 2)$. Свап $i=2$: $(4, 3) \to (3, 4)$. Свап $i=4$: $(4, 2) \to (2, 4)$.

После: $A = [1, 3, 3, 4, 2]$, $B = [1, 2, 4, 5, 4]$. $|set(A)| = |{1,3,4,2}| = 4$, $|set(B)| = |{1,2,4,5}| = 4$. Сумма 8.

Нужно другое: $A = [1, 3, 4, 5, 2], B = [1, 2, 3, 4, 4]$ → сумма 9. Это маска $\{1, 3, 4\}$: позиции 1, 3, 4. Mask = $0b11010 = 26$.

Проверим: mask=26, биты 1, 3, 4 (0-indexed). Свап $i=1$: $(2, 3) \to (3, 2)$. Свап $i=3$: $(4, 5) \to (5, 4)$. Свап $i=4$: $(4, 2) \to (2, 4)$.

$A = [1, 3, 4, 5, 2]$, $B = [1, 2, 3, 4, 4]$. $f(A) = 5$, $f(B) = 4$. Сумма 9. ✓

Пример 2

$n = 7$, $a = [2, 2, 4, 4, 5, 5, 5]$, $b = [1, 3, 3, 2, 1, 6, 6]$. Ожидается 12.

$f(a') + f(b') = 6 + 6 = 12$. Перебор $2^7 = 128$ вариантов — подтверждает.

Пример 3

$n = 7$, $a = [12, 3, 3, 4, 5, 6, 4]$, $b = [1, 2, 13, 8, 10, 13, 7]$. Ожидается 14.

Тоже проверяется перебором.

---

Крайние случаи

1. Все значения различны. $f(a) + f(b) = 2n$. Свапы не меняют.

2. Все одинаковые. $a = b = [k, k, \ldots, k]$. $f(a) = f(b) = 1$. Свапы не помогают. Сумма $2$.

3. $n = 1$. Пара $(a_1, b_1)$. Если $a_1 = b_1$ — сумма $2$ (каждый массив 1 элемент). Иначе — тоже $2$ (один в $a$, один в $b$, оба различные). Свап ничего не меняет (только две одинаковые конфигурации).

4. Большие $n$ (до $10^5$). Перебор $2^n$ не пройдёт. Нужно полное решение через граф — см. идею выше.

---

Типичные ошибки

1. Попытка жадно свапать по одному. Жадность «если свап увеличит сумму — свапаем» даёт локальный оптимум, но не глобальный. Контрпример — любой цикл из 3 ребер: локально поменять ориентацию одного ребра не улучшит, но глобальная переориентация всего цикла в одну сторону улучшает.

2. Забыть, что вершина с одним ребром приносит вклад ≤ 1. Не 2. Если увидеть это только в конце — переделывать задачу придётся с нуля.

3. Не учесть одинаковые элементы $a_i = b_i$. Такое ребро = петля в графе. В ориентированном графе петля $v \to v$ даёт $v$ и входящее, и исходящее — вклад $2$. Но значение входит в $a$ и $b$ один раз — и в сумме считаем $2$. Никаких особых проблем, но удобно замечать.

4. Перебор $2^n$ для $n > 20$. Забыть, что такой алгоритм не проходит полный тест.

---

Сложность

• Перебор: $O(2^n \cdot n)$. Подгруппа 1 ($n \leq 18$), 17 баллов.
• Полное решение: $O(n)$ через разложение графа на циклы и пути с «клонированием» значений высокой частоты.

---

Что ещё полезно потренировать

Задачи на ориентацию графов и разложение на циклы/пути:

• Codeforces 508D «Tanya and Password» — восстановление эйлерова пути.
• Codeforces 723E «One-Way Reform» — ориентация рёбер для эйлерова цикла.
• Codeforces 547D «Mike and Fish» — ориентация на двудольном графе, симметричная задача.
• Codeforces 1178F2 «Long Colorful Strip (Hard)» — сложная DP, но с характерным разложением на сегменты.

Общий мотив: «задача превращается в граф, и требуется умная ориентация или разложение на элементарные объекты (пути, циклы)».

---

Итого

• Сведение: пара индексов $(a_i, b_i)$ — ребро графа между значениями; свап = выбор ориентации.
• Цель: максимизировать сумму «вершин с исходящим» и «вершин с входящим» — для вершины степени $\geq 2$ вклад $2$, для листа $1$.
• Простое решение: перебор $2^n$ масок, $O(2^n \cdot n)$. Подгруппа 1.
• Полное решение: разложение графа на циклы и пути (с предварительным клонированием вершин высокой степени), ориентация каждого компонента отдельно. $O(n)$.
• Ловушки: локальная жадность не работает; забыть про вклад $1$ для листьев; $a_i = b_i$ — это петля.