Input Jumbled Key#12830

Input Jumbled Key (Розбір)

Олег Валлас

Назвемо паролі, які містять рівно одну парну цифру, парними, а ті, що складаються повністю з непарних цифр — непарними. Назвемо непарний пароль сусіднім до парного, якщо непарний може відкрити замок замість парного (за умовою завдання), тобто відрізняється рівно в одній цифрі на одиницю.

За умовою необхідно щоб після введення списку паролів замок обов'язково відкрився. Оскільки ми не знаємо, який саме пароль правильний, необхідно підібрати список паролів мінімального розміру (а серед них лексикографічно мінімальний) так, щоб для кожного пароля з вводу в нашому списку був присутній або він сам, або сусідній до нього непарний.

Спочатку покажемо, як знайти розмір відповіді (поки забудемо що вона повинна бути лексикографічно мінімальною).

Твердження 1: коректна множина паролів мінімального розміру завжди може бути складена тільки з непарних паролів, сусідніх із вхідними.

Дійсно:

  • парний пароль може відкрити тільки себе, тому його завжди можна замінити на сусідній непарний і кількість "покритих" паролів не зменшиться.

  • паролі, які не є сусідніми з вхідними, очевидно брати не вигідно взагалі, тому що вони нічого не можуть відкрити.

Тоді побудуємо граф, в якому непарні паролі, сусідні з вхідними, будуть вершинами, а вхідні паролі — ребрами (у кожного парного пароля якраз рівно 2 сусідніх).

Твердження 2: отриманий граф є дводольним.

Коли ми переходимо по будь-якому ребру цього графа, в паролі рівно одна цифра збільшується або зменшується на 2. Не складно помітити, що для того щоб прийти з вершини в себе нам завжди доведеться зробити парну кількість таких операцій. Це означає, що всі цикли в графі парної довжини, значить він дводольний за визначенням.

Отже, ми хочемо вибрати мінімальну кількість непарних (виходячи з твердження 1) паролів, щоб покрити всі парні. Це ні що інше, як мінімальне вершинне покриття в отриманому графі. Оскільки граф дводольний, розмір його мінімального вершинного покриття дорівнює розміру його максимального парування. Його можна знайти, наприклад, алгоритмом Куна.

Тепер ми знаємо розмір відповіді, покажемо як знайти сам лексикографічно мінімальний набір паролів цього розміру.

Зауважимо, що в лексикографічно мінімальному наборі можуть бути як непарні, так і парні паролі (наприклад, 2й тест з умови). У твердженні 1 говорилося лише про мінімальний розмір відповіді, але така відповідь не обов'язково буде лексикографічно мінімальною.

Саму відповідь будемо відновлювати жадібно.

Переберемо все потенційних кандидатів в порядку зростання. Видалимо з графа відповідну поточному паролю вершину або ребро. Порахуємо в отриманому графі розмір максимального парування. Якщо він залишився таким самим, то поточний пароль взяти не вийде. Якщо ж розмір зменшився на 1, то це означає, що ми зможемо покрити решту паролів набором розміру на один менше. Тоді візьмемо поточний пароль у відповідь.

Якщо після кожного видалення шукати максимальне парування заново, часова складність буде O(3N \times 2N \times (3N + 2N)) = O(N ^ 3), тому що в графі вершин і ребер. Це занадто повільно, тому будемо перераховувати цей розмір більш оптимально. Спочатку знайдемо будь-яке парування. Тепер якщо ми розглядаємо пароль, який відповідає:

  • ребру не з парування: просто пропустимо цей пароль. Очевидно, що після видалення такого ребра розмір парування не зміниться;

  • вершині, що не є інцидентною жодному ребру з парування: просто пропустимо цей пароль з аналогічних міркувань;

  • ребру з парування: видалимо ребро і запустимо пошук шляху розширення з обох кінців ребра;

  • вершині, що є інцидентною ребру з парування: видалимо вершину і запустимо пошук шляху розширення з протилежного кінця цього ребра.

Оскільки пошук шляху розширення працює за O(V + E), підсумкова складність рішення буде O((3N + 2N) \times (3N + 2N)) = O(N ^ 2).