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