Так как остальные задачи я не то что не пытался решить, а даже не читал, публикую те решения, которые узнал
Задача A. Домино
Для начала поймём, что на квадраты 2x2 всё поле разбивается однозначно и это можно сделать жадным алгоритмом. Теперь у нас есть 14 квадратов. Далее можно сделать необязательное преобразование, от которого лично мне стало жить проще: построим граф на 14 вершинах, ребро между вершинами будет тогда и только тогда, когда у соответствующих квадратов есть общая доминошка. В принципе, это даже какой-то оптимайз по времени, но не суть важно.
Теперь задача такова: есть граф на 14 вершинах, надо раскрасить их в цвета от 0 до 6 так, чтобы все рёбра были разными (два ребра одинаковы, если цвета концов совпадают). Утверждается, что решение - перебор. Перебираем цвет первой, второй, третьей, ..., 14й вершины, на каждом шаге проверяем, что у нас не появилось ребро той же расцветки, что уже было (естесственно, делаем это массивом bool'ов). После чего останется вывести ответ и какую-нибудь раскраску.
Однако это решение может не зайти по времени. Остался один мощный оптимайз. Заметим, что, по сути, разницы между цветами нет. Значит, цвета в раскраске можно переставлять как угодно. Теперь научимся считать количество ответов с точностью до перестановок цветов, а в конце домножим его на 7!=5040. Это просто: достаточно ввести условие, что цвет очередной вершины либо встречался раньше, либо идет сразу после максимального использованного цвета. Например, после цветов 0 1 2 1 0 2 могут идти только цвета 0..3.
Чтобы уверовать в то, что это решение зайдёт, можно грубо оценить количество ответов. Каждая вершина раскрашена в один из семи цветов, каждый цвет встречается ровно два раза, плюс мы не учитываем различные перестановки. Итого получается
, что, очевидно даже при отсечении на последнем шаге рекурсии, влезает в TL.
Теперь задача такова: есть граф на 14 вершинах, надо раскрасить их в цвета от 0 до 6 так, чтобы все рёбра были разными (два ребра одинаковы, если цвета концов совпадают). Утверждается, что решение - перебор. Перебираем цвет первой, второй, третьей, ..., 14й вершины, на каждом шаге проверяем, что у нас не появилось ребро той же расцветки, что уже было (естесственно, делаем это массивом bool'ов). После чего останется вывести ответ и какую-нибудь раскраску.
Однако это решение может не зайти по времени. Остался один мощный оптимайз. Заметим, что, по сути, разницы между цветами нет. Значит, цвета в раскраске можно переставлять как угодно. Теперь научимся считать количество ответов с точностью до перестановок цветов, а в конце домножим его на 7!=5040. Это просто: достаточно ввести условие, что цвет очередной вершины либо встречался раньше, либо идет сразу после максимального использованного цвета. Например, после цветов 0 1 2 1 0 2 могут идти только цвета 0..3.
Чтобы уверовать в то, что это решение зайдёт, можно грубо оценить количество ответов. Каждая вершина раскрашена в один из семи цветов, каждый цвет встречается ровно два раза, плюс мы не учитываем различные перестановки. Итого получается
, что, очевидно даже при отсечении на последнем шаге рекурсии, влезает в TL.Задача B. Надмножество
Задача была немножко (или множко?) идейной. Одним из возможных решений является разделить множество точек пополам веритикальной прямой (если не получается ровно, та так, чтобы разница была минимальна), решить задачу рекурсивно для двух половин, и добавить на разделяющую прямую точки со всеми встречающимися в ответах для половин y'ами.
Докажем корректность. Если точки лежат в одной половине, всё мы верим, что верно решили подзадачу. Если же они лежат в разных половинах, то их bounding box пересекает нашу прямую, и в точках пересечения выделенные точки есть (посльку их y'и встречались слева и справа).
Прошу сообщество рассказать остальные задачи в комментариях
Докажем корректность. Если точки лежат в одной половине, всё мы верим, что верно решили подзадачу. Если же они лежат в разных половинах, то их bounding box пересекает нашу прямую, и в точках пересечения выделенные точки есть (посльку их y'и встречались слева и справа).
Прошу сообщество рассказать остальные задачи в комментариях
А не получиться ровно пополам может очень просто: точек нечётно :)
Пусть a[i] - частота появления i участников
Тогда (\sum это сумма по всем i)
\sum a[i]*p[i] => max
\sum a[i]*i <= n/2
\sum a[i] = 1
любое a[i] >= 0
Это задача линейного программирования с двумя ограничениями, и, если я ничего не путаю, то в ее решении не более 2 отличных от нуля переменных. Можно их перебрать и свести задачу к наилучшей из
x*p[i] + y*p[j] => max
x*i + y*j <= n/2
x+y = 1
x,y >= 0
и дальше решить это, разобрав 2 случая
С линейным программированием все и правда легко заканчивается.
Поискал примеры. Вот: решение учатника LayCurse в прошлой правке. Проще положить исходник, чем объяснять.
Получаем решение за N^3.
Далее, если доказывать это дело строго, можно получить решение намного проще: возьмем длинный префикс последовательности, мало отличающийся (на eps) от предела "лучшей" последовательности (формально, в условии задачи не было сказано, почему такая существует, но склеивая последовательности, аппроксимирующие супремум, мы ее получим), кроме того, итоговое количество финалистов в котором тоже ограничено константой, не зависящей от длины префикса (из условия возрастания pi можно считать, что такой префикс найдется). Придумаем просто устроенную последовательность, которая хуже разве что на O(eps) и устремим eps к нулю.
Возьмем пару +T и - S изменений количества финалистов в префиксе, которая встречается много раз. Если T, S > 0, то можно переставить их так, что подряд идут S прибавлений и T вычитаний, получив тем самым цикл. Проделывая этот трюк далее, мы получим много циклов и маленький остаток (не зависящий от длины префикса). Значит, максимальный по средней вероятности цикл несильно хуже предела, чего мы и добивались: повторяя это цикл с самого начала новой последовательности (для этого еще может понадобиться немного финалистов в начале, это, разумеется, не влияет на предел), получаем последовательность с пределом, равным средней вероятности данного цикла. Так как количество таких циклов конечно, мы доказали, что некоторая последовательность нашего вида является лучшей.
Решение: перебираем пары + T, - S, выбираем ту, которая дает среднюю вероятность лучше (не забываем еще про бесконечную последовательность из + 0, которая возможна при четном N).
Итого - N^2.
Здоровская задача, как, впрочем, и остальные в этом прекрасном раунде.
P. S. Рассуждение не проверял, поправьте и спросите, если что не так.
Позже напишу более подробный разбор.
Может ли проходить такое решениев в В, или я неправильно понимаю задачу? :
Отсортируем все точки сначала по абсциссе, по том по ординате (причем stable). Рассмотрим две соседние горизонтальные прямые, на которых есть точки. Для каждой точки нижней прямой ставим точку с той же абсциссой на верхнюю и наоборот. Пересматривая так по очереди все пары соседних прямых, на которых есть точки, сверху вниз, получим требуемое надмножество. Проблема только в учете повторяющихся точек на последней рассмотренной прямой, что можно реализовать вспомогательным стеком за N2. Если при этом учитывать отсортированность проставляемых точек, то это можно делать за линию, тогда все решение уложится в N*logN за счет сортировок.
Написал, весь контест дебажил и продолжаю (ушел за молотком - выпрямлять руки)
Не размножаем...
За контр-пример - большое спасибо!