Нелепости

[major_m]

Ездить в такси без носков.
Кушать суши, не чувствуя запаха.
Решать задачу из мультика несколько дней.

Comments

[ext_1301353]

Я, вроде бы, умею решать частный случай, когда разрешенные пары образуют лес (за линию).

[major_m]

Интересно, а как ты этот случай решаешь?

Я подумал немного над ним. Можно сделать так. Возьмем произвольный лист, пусть там хочет оказаться значение x. Если x уже на своем месте, то просто забудем про этот лист. Если нет, но x лежит в соседе листа, делаем своп. Если x где-то далеко, то на лист забиваем и ставим звонок вспомнить про него, когда x окажется в соседе. Надо только подумать, почему это не зависнет, когда решение существует...

[ext_1301353]

Подвесим дерево и рассмотрим какое-нибудь поддерево.
Есть три случая:
1) из поддерева ничего не "торчит". Тогда отрезаем его и решаем независимо
2) ровно один элемент должен уйти наверх, и ровно один должен прийти на его место. В этом случае решаем подзадачу, предположив что такой обмен можно сделать в момент когда лишний элемент находится в корне поддерева.
3) в остальных случаях, ответ отрицательный, потому что у нас максимум один своп с этим поддеревом

Теперь осталось понять, можно ли разрулить поддеревья заданной вершины. это можно сделать симуляцией, заменив каждое поддерево 2го типа на одну вершину, с соответствующим "лишним" элементом

[sorphy_san]

Неожиданно оказаться в такси и без носков.

[krevetka_flo]

С опозданием поздравляю… Съем-ка за Вас черешенку размороженную)