1106A - Lunar New Year and Cross Counting
Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.
Асимптотика O(n2)
Код:49284766
1106B - Lunar New Year and Food Ordering
Заметим, что каждый человек получит либо dj блюд типа tj, либо rtj блюд типа tj и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.
Асимптотика 
Код:49285005
1106C - Lunar New Year and Number Division
Для начала заметим, что в каждой группе должно быть ровно два элемента, так как (a + b)2 > a2 + b2 для положительных a и b
Покажем, что ai и bi должны стоять на "противоположных" позициях в отсортированном массиве, так как
То есть нам надо минимизировать третье слагаемое. Теперь такой выбор ai и bi следует из транснеравенства (доказательтво).
Асимптотика 
Код:49285168
1106D - Lunar New Year and a Wander
Допустим, мы знаем префикс ответа длины i. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером.
Это можно сделать используя bfs с приоритетной очередью.
Асимптотика 
Код:49285447
1106E - Lunar New Year and Red Envelopes
Задача решается методом динамического программирования. Обозначим за dp[i][j] минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени i и Алиса уже отвлекла его j раз.
Тогда из dp[i][j] можно перейти в dp[i + 1][j + 1] (если Алиса отвлекает его на i-том ходе) и в dp[dchoice + 1][j], где dchoice — d конверта, который выберет Боб.
Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию w. Тогда мы сможем узнавать выбор Боба на каждой итерации за 
.
Асимптотика 
Код:49285694
1106F - Lunar New Year and a Recursive Sequence
В разработке.
