Через неделю стартует первый этап ACM ICPC в Украине. В связи с этим, я просматривал задачи и результаты прошлых лет, и наткнулся на одну интересную задачу с первого этапа позапрошлого года.
Примечательна она тем, что на контесте по ней было 15 удачных посылок (сравнительно не самое малое число), однако из первых 60-ти команд-участниц, ни одна команда эту задачу так и не сдала. То-есть в основном её порешали весьма слабые команды, а сильные не осилили)
Условие задачи весьма простое: Есть перестановка из n чисел. Два игрока по очереди стирают по одному числу, пока не останется два числа. Какое из оставшихся чисел меньше, тот игрок и победил. Ну и стандартный вопрос: кто победит при оптимальной игре?
Вот собственно полное условие задачи.
Сам я так и не придумал, как решать эту задачу. Поэтому и спрашиваю здесь.
UPD. неправильно прочитал условие ><
Вроде как почти всегда выигрывает тот, кто ходит последним. Иной результат может быть только если максимальная возрастающая или максимальная убывающая подпоследовательность по длине больше половины (на 1 или 2, в зависимости от того, кто ходит).
Блин возрастающей и убывающей последовательностей недостаточно: у перестановок [8, 7, 6, 4, 5, 0, 1, 2, 3] и [8, 1, 6, 5, 0, 3, 2, 4, 7] длины макс. возрастающих/убывающих 4/5 соответственно, но первая — выигрышная, а вторая — проигрышная.
обе выигрышные вроде
Давай сыграем во вторую :)
Я возьму 8, ты 7, потом я возьму 6, и независимо от твоего ответа 5. Останется 1,0,3,2,4 без какой-то одной. В один из ходов ты должен будешь забрать 4, будем считать, что ты ее и забрал в тот ход. Ну а 1,0,3,2 ты не можешь сделать убывающей
Мне нравится твоя манера игры. Не пробовал так играть в шахматы?
Шахматные задачи так и играются
Можно даже с доказательством: если длина монотонной возрастающей подпоследовательности x > n/2, то можно разбить не меньше, чем на x убывающих (Дилуорс). Среди них будет что-то длины 1, надо этот элемент убрать, то что останется можно будет разбить не больше, чем на x-1 убывающих, значит макс возрастающая уменьшилась
Да, с перебором для n<=10 такое решение сходится.
Точно, нашел баг у себя в переборе
Круто, работает, спасибо! =)
На сколько я помню, мы потом узнавали решения, и там проходили какие-то явные лажы, на которые сразу контр тест строится, отсюда и много АС внизу таблицы.
По поводу того, что там проходило — на CF есть обсуждение.
Пример решения, которое проходило.И там же есть и другие похожие, и контпримеры к ним, и еще некоторые интересные вещи.