На сайте http://www.azspcs.net/ завершился очередной контест.
Контест трехмесячный, однако на данный сайт я наткнулся всего несколько недель назад. Решил поучаствовать, дабы, так сказать, распробовать новый вид соревнований.



Задача понравилась. При своей простой формулировке она имеет мозголомную сложность. Суть задачи в следующем.

Возьмем какую нибудь перестановку длины n, например, 3, 6, 5, 1, 4, 2. Будем делать с ней следующую вещь. Пусть первое число в перестановке k (в данном случае, k = 3). Тогда запишем первые k чисел в обратном порядке. Эту операцию будем повторять пока первым числом не окажется единица. Для предложенной перестановки получим:

5, 6, 3, 1, 4, 2
4, 1, 3, 6, 5, 2
6, 3, 1, 4, 5, 2
2, 5, 4, 1, 3, 6
5, 2, 4, 1, 3, 6
3, 1, 4, 2, 5, 6
4, 1, 3, 2, 5, 6
2, 3, 1, 4, 5, 6
3, 2, 1, 4, 5, 6
1, 2, 3, 4, 5, 6

Итого - 10 переворачиваний. Задачей участников было для некоторых n найти перестановки, у которых количество переворачиваний как можно больше.

Задача очень сложна, для решения в лоб нужно перебрать все n! перестановок, для каждой из них посчитать количество переворачиваний и выбрать максимум. При ограничениях n до 97 даже если все вещество Вселенной переплавить в суперкомпьютеры, не хватит времени жизни Вселенной чтобы просчитать все варианты (впрочем, тут я утрирую, на самом деле я не подсчитывал :D).

Но - в данной соревновании не нужно находить лучшее решение, достаточно найти хорошее.

Для маленьких n я написал тупой перебор, а для больших написал несколько генетических алгоритмов, решения найденные ими улучшал локальным перебором. Это позволило добраться мне до 58 строчки итоговой таблицы http://www.azspcs.net/Contest/Cards/Standings. Ну, неплохо для первого участия в подобных соревнованиях :D.

Кто что может интересного сказать по этому поводу? Кто участвовал и как пытался набрать свои 25 баллов?:)