Задача: даны два множества точек на плоскости (оба размером N), нужно найти совершенное паросочетание с минимальным весом самого тяжелого ребра в нем (вес ребра — очевидно, Евклидово расстояние). Я умею решать Куном с бинпоиском по весу самого тяжелого ребра за O(N³ logN). Вопрос: как решить эту задачу за чистый куб путем добавления в алгоритм какой-то жадности? Хопкрофта-Карпа и Диница прошу не предлагать. Ответ: вот так.

Задача о поиске совершенного паросочетания в регулярном двудольном графе объяснялась в харьковской ЗКШ в этом году, но только для тех графов, в которых степени каждой вершины являются степенями двойки. Вопрос: как решать эту задачу для графов с произвольными степенями вершин? Применение алгоритма Хопкрофта-Карпа очевидно, но мне кажется, что существует что-то побыстрее.

Задача: дан регулярный граф, нужно найти в нем гамильтонов цикл. Вопрос: существует ли алгоритм, который гарантированно найдет этот гамильтонов цикл за полиномиальное время, если он имеется?

Эта задача с Тимуса имеет очевидное решение через паросочетание. Вопрос: можно ли обойтись без паросочетания и решить задачу жадно? Ответ: да, можно, а я тупой идиот, потому что думал как раз о таком решении, но не удосужился проверить 3 случая.