В G такое работает 1.5с на джаве на Я.Контесте. Найдем для каждой вершины ближайшие ~20 и оставим только эти ребра. Дальше запустим Крускала. Чтобы найти ближайшие точки, разобьем все на одинаковые квадраты так, чтобы в каждом квадрате в среднем было по ~6 точек. Для каждой точки рассмотрим все точки из 8 соседних, а также того квадрата, в котором она находится. Отсортируем по расстоянию, возьмем первые 20.

В I вроде бы все просто: при больших k ответ N, иначе узнаем вероятность того, что первый предмет будет потроган ровно k раз через Х ходов (динамикой, для X < MAGIC). Дальше для каждого Х ответ по линейности матожидиния что-то вроде N*(1-(1-p)^X).

В I можно было формулу вывести:
, где q = 1 - p.
Чтобы вывести, переберем номер раунда, на котором все закончится и просуммируем матожидания.

В G можно написать алгоритм Прима со следующими оптимизациями:

• посортируем все точки по возрастанию x;
• поддерживаем set текущих расстояний от еще свободных точек до уже построенного дерева;
• пусть на очередной итерации мы выбрали вершину под номером v в отсортированном массиве, тогда будем обновлять расстояния не до всех свободных точек, а только до тех, которые находятся под номерами [v — BOUND, v + BOUND] в отсортированном массиве точек.

Если в таком решении поиграться с BOUND то можно получить WA, TL на тестах в районе 25-30. Однако, при локальном тестировании оказывается, что если выбрать BOUND >= 1000, то алгоритм почти всегда находит правильный ответ. При этом, происходит порядка 5 миллионов добавлений в set и порядка 50 миллионов подсчета расстояний между парой точек.

Теперь улучшим приведенный алгоритм — на очередной итерации будем считать расстояние только до тех точек из интервала [v — BOUND, v + BOUND], для которых abs(p[i].y — p[v].y) <= LIMIT. Здесь под p[index].y обозначаем y-координату точки под номером index в отсортированном массиве. Такое отсечение позволяет существенно сократить количество подсчетов расстояний между парами точек, а также где-то в два раза уменьшает количество обращений в set и уже проходит. При этом следует отметить, что такое решение будет давать неправильный ответ, если точек слишком мало, но при n >= 10000 уже все в порядке (для маленьких n можно просматривать все точки в интервале [v — BOUND, v + BOUND]).

Мое решение получило ОК при BOUND = LIMIT = 1000.

Ответ на задачу , где r — ранг матрицы. При больших значениях r ответ быстро стремится к 1/2, поэтому не нужно делать Гаусса до конца.

Do BFS from a random start cell, fill n/2 cells, then count the number of border cells (unvisited cells that have a visited neighbor, i.e. we have to remove the border cells in order to disconnect the region of visited cells from the rest). If the number of border cells is good ( <= 3/2sqrt(n)), done, if not, take another random starting cell and repeat.

Другой подход — будем пилить фигуру пополам прямой случайного направления. Рассмотрим положение прямой, которое проходит через n/2-ую точку в порядке заметания, после этого надо непосредственно "распилить" рёбра, пересекающие нашу прямую. Для этого выкинем все левые и верхние, например, концы этих рёбер. Если их не больше чем сколько там надо, победа. Получается проверка одной прямой ровно за O(N).

100 случайных прямых хватает.

Разобъем всю фигуру на полосочки с одинаковым x. Будем вырезать только полосочки целиком. Понятно, что если мы удалим все клетки с фиксированной координатой x, то весь граф разобъется на части. Для начала попробуем вырезать только одну полоску. Если не получилось (то есть нужно вырезать слишком много клеток), напишем динамику по полоскам — сколько минимум клеток нужно вырезать, чтобы не было подряд идущих связных кусков содержащих более чем n/2 клеток.

После этого проделаем то же самое, но будем удалять полоски с фиксированным y.

На самом деле хватает достаточно большого цикла, к которому из остальных сходится. Мы рандомом построили цикл из порядка 37к вершин

Почему из того, что любая ячейка памяти посещается, следует, что робот посещает все клетки поля?

И как сделан чекер к задаче, кстати? Не за 3^20 же?

Узнать у авторов в личном порядке, никаких официальных разборов нет ;)