Собственно сабж.

У меня осталась одна попытка на финал ACM-ICPC, и хотелось бы в следующем сезоне съездить и побороться за что-нибудь в финале. В связи с этим ищу команду. Если кто вдруг может чего-нибудь предложить интересного в этом плане, пишите в лс =)

Через неделю стартует первый этап ACM ICPC в Украине. В связи с этим, я просматривал задачи и результаты прошлых лет, и наткнулся на одну интересную задачу с первого этапа позапрошлого года.

Примечательна она тем, что на контесте по ней было 15 удачных посылок (сравнительно не самое малое число), однако из первых 60-ти команд-участниц, ни одна команда эту задачу так и не сдала. То-есть в основном её порешали весьма слабые команды, а сильные не осилили)

Условие задачи весьма простое: Есть перестановка из n чисел. Два игрока по очереди стирают по одному числу, пока не останется два числа. Какое из оставшихся чисел меньше, тот игрок и победил. Ну и стандартный вопрос: кто победит при оптимальной игре?

Вот собственно полное условие задачи.

Сам я так и не придумал, как решать эту задачу. Поэтому и спрашиваю здесь.

Банальная задача: Дано n точек на плоскости. Необходимо найти наибольшее количество точек, лежащих на одной прямой.

Вопрос: Решаема ли эта задача быстрее, чем за , или же О(n²) — с хеш-мэпом.

Решаема ли такая задача за полиномиальное время?

Дан полный взвешенный граф из n вершин. Веса рёбер даны. Два игрока по очереди удаляют из графа по 1 вершине, пока не останется 2 вершины. Цель первого игрока — максимизировать вес оставшегося ребра, а второго — минимизировать. Определить вес оставшегося ребра при условии, что оба игрока играют оптимально.