Тройка задач (и может быть перестановки)

[ens_a_se]

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

Comments

[sleepy_drago]

представление в виде графа выглядит притянутым за уши. Лобовые решения 1 и 2 представляют собой hash_map<1..N, count> и проход по содержимому, что дает О(N). 3ю не понял что значит "пропущенное".

[ens_a_se]

Ну а по памяти-то тоже дает линию. С графом можно сделать без доп памяти все три.

[sleepy_drago]

насчет фиксированной памяти будет любопытно теоретически. имхо практикческие решения с перфект хешом на массиве все победят =)

[ens_a_se]

Да тут натуральные числа и диапазон известен, массив будет как перфект хэш таблица. На практике, через граф быстрее работает - это задача с leetcode, там показывается время на тестах и можно сравнить