Легенда: на прекрасной солнечной улице, где-то в Сочи, живут чиселки в своих уютных домиках. Конечно же они любят общаться между собой. А именно есть несколько групп друзей, в каждой из которых состоят одинаковые числа. Но к сожалению числа не довольны тем, что им приходиться проходить мимо домов незнакомых чиселок, чтобы попасть к своим друзьям. Вам поручили снести несколько домов и выселить числа которые там живут (сначала выселить, потом снести), так, чтобы все оставшиеся числа были довольны. Но т.к. выселение чисел и разрушение домов плохо влияют на имидж улицы, то вы решили уничтожить как можно меньше домов.
Задача: есть массив из целых чисел (все числа от 1 до n). Надо удалить как можно меньше чисел, чтобы не было такой тройки индексов, что 1 <= i < j < k <= n и a[i] == a[k] и a[i] != a[j]. 1 <= a[i] <= n. Ограничения на n могут быть наверное почти любыми, т.к. я не смог придумать решение быстрее чем за полином. Возможно это вообще np полная задача и её нельзя решить быстрее.
Вероятно если написать дп вида: маска какие числа есть и на какое число всё это заканчивается, то можно вероятно написать meet in the middle, т.к. если число встречается один раз, то оно нам никак точно не помешает, а иначе оно встречается хотя бы 2 раза, т.е. всего различных "интересных" чисел будет n / 2, а значит если n будет порядка 40, то маска будет до миллиона и решение будет работать.
