Задача А. Новогодний стол
Тарелки должны касаться края стола, а значит, их центры должны лежать на окружности радиуса R - r (см. рисунок).
В случае если тарелки имеют наибольший возможный радиус для данного стола, их центры будут располагаться в вершинах правильного n-угольника, вписанного в эту окружность. Задача сводится к тому, чтобы найти длину стороны вписанного правильного n-угольника и сравнить ее с 2r. Формулу для длины стороны a = 2(R - r)sin (π / n) нетрудно вывести. Для этого нужно рассмотреть прямоугольный треугольник, нарисованный зеленым цветом.
При реализации нужно было аккуратно выделять случай, когда выполняется равенство r = (R - r)sin(π / n) (*). Из-за вычислительной погрешности правая часть может получиться больше левой, что приведет к ответу "NO" вместо "YES". Сравнение в таких случаях нужно проводить с участием маленького ε:
a + ε < b вместо a < b ,
a < b + ε вместо a ≤ b.
Константу ε нужно выбирать таким образом, чтобы она была меньше возможной разности между точными значениями a и b, если они не равны. В частности, при вычислениях по формуле (*) с учетом ограничений задачи эта разница может составить примерно 7· 10 - 7. Поэтому ε = 10 - 7 достаточно, а ε = 10 - 6 - уже нет.
В очередной раз акцентирую внимание на том, что выбор ε зависит от конкретных формул, по которым происходят вычисления и сравнения. Разные решения могут проходить и не проходить с одним и тем же ε .
Задача носила чисто реализационный характер. Заметим, что номер отправленной открытки однозначно определяется номером друга и множеством открыток, имеющихся у Александра в данный момент. Разберем пример из условия.
| 1 | 2 | 3 | 4 |
{1} | - | 1 | 1 | 1 |
{1, 2} | 2 | 1 | 1 | 1 |
{3, 1, 2} | 3 | 3 | 1 | 3 |
{3, 1, 2, 4} | 3 | 3 | 1 | 3 |
Первый столбец таблицы содержит множества открыток, получающиеся у Александра после получения каждой очередной открытки. Номера в множествах записаны в порядке приоритетов Александра. Каждый i-й из следующих четырех столбцов содержит номера открыток, которые получит i-й друг из соотвествующих множеств. Наша цель - выбрать для каждого друга самую предпочтительную открытку из его столбца.
Заметим, что чтобы по текущему множеству Александра и номеру друга определять, какая открытка отправится этому другу, не обязательно знать все множество Александра. Достаточно только двух самых приоритетных открыток. Поэтому для каждого момента времени найдем две самых приоритетных открытки среди имеющихся. Используя их, определим, какая из них отправится каждому другу (посчитаем столбцы таблицы). Потом выберем элемент с максимальным приоритетом в каждом столбце. Получаем решение за O(n2).
Решение 1. Предположим, что ответ на задачу k. Если среди заданных чисел более k одинаковых, то ясно, что мы не сможем их все использовать (потому что мы не можем использовать в одном снеговике одинаковые комы), поэтому оставим из таких комов k, остальные отбросим. Далее отсортируем радиусы в порядке невозрастания. После этого любые два кома с номерами i и k + i различны. Составим снеговиков из комов с номерами (1, k + 1, 2k + 1), (2, k + 2, 2k + 2), (3, k + 3, 2k + 3) и т.д. Если общее количество оставшихся комов не меньше 3k, то у нас всегда получится сделать k снеговиков. Теперь, когда мы умеем отвечать для фиксированного k на вопрос, можно ли составить k снеговиков, можно подбирать k бинарным поиском.
Решение 2. Посчитаем количества комов каждого размера и будем жадно выбирать три наибольшие кучки, брать из них по одному кому и отбрасывать их, и так до тех пор, пока возможно. Почему это правильно? Пусть ответ на задачу k. Если в каких-то кучках больше k комов - будем считать, что их там k, потому что остальные комы мы все равно не используем. Правильность алгоритма докажем через
Утверждение: если в каждой кучке ≤ k комов, при этом суммарное количество комов ≥ 3k, то можно сделать ход по алгоритму.
Утверждение верно, потому что по принципу Дирихле найдутся хотя бы три непустые кучки. Если есть хотя бы 3 кучки размера k - можно беспрепятственно сделать k шагов алгоритма. Если таких кучек одна или две - первым ходом мы обязательно уменьшим их и перейдем к ситуации для k - 1. Если кучек размера k вообще нет, мы тоже после первого шага получим кучки размером ≤ k - 1 и суммой ≥ 3(k - 1). Таким образом, мы всегда сможем сделать k шагов и получить ответ k.
С точки зрения реализации второго решения удобно посчитать количества кучек с каждым размером комов (при помощи сортировки и "сжатия координат") и использовать set для работы с этими количествами. Время работы обоих решений -
.
Решение 1 (жадность). Оптимальный порядок решения задач - в порядке возрастания (неубывания) сложности. При этом задачи, решенные до Нового года, нужно отправлять в 0:00, решенные после Нового года - сразу после их решения.
Почему такой порядок оптимальный, докажем методом спуска. Общая схема рассуждений такова: предположим, что имеется оптимальный ответ, в котором задачи решаются не в порядке возрастания сложности. Покажем, что от него можно перейти ("спуститься") к другому варианту, который будет не менее оптимальным. В итоге такими шагами придем к отсортированному варианту.
Итак, предположим, что в оптимальном ответе есть пара задач, сложности которых идут в порядке убывания. Тогда есть две задачи, решаемые подряд и обладающие этим свойством. Предположим, они обе решаются до Нового года. Тогда от смены их порядка суммарное штрафное время не изменится (а значит, не ухудшится). Если обе задачи решаются после Нового года, то их вклад в общее штрафное время (T + ai) + (T + ai + aj), где T - время начала решения первой из них (с номером i), ai - время решения первой задачи, aj < ai - время решения второй задачи. При перестановке этих двух задач получаем штрафное время (T + aj) + (T + aj + ai), что меньше чем (T + ai) + (T + ai + aj). Осталось рассмотреть случаи, когда одна из соседних задач, стоящих в "неправильном" порядке, "пересекает Новый год". Эти случаи рассматриваются аналогично.
В случае если Геннадий не успевает решить все задачи за отведенное время, следует выбирать наибольшее возможное количество самых простых задач. Действительно, не имеет смысла решать более сложную задачу и не решать более простую: замена большего ai на меньшее не ухудшит ответ. Строгие рассуждения можно провести тем же методом спуска.
Решение 2 (динамика). Сначала, как и в предыдущем решении, выберем наибольшее количество самых простых задач, которые Геннадий успеет решать за отведенное время. Остальные задачи отбросим. Переберем задачу, которая будет решать непосредственно в Новый год (0:00). Остальные задачи, кроме нее, нужно разбить на два множества, одно из которых решается до Нового года, другое - после. Задачи во втором множестве нужно решать в порядке возрастания сложности (известный факт для тех, кто участвует в соревнованиях по правилам ACM). В первом множестве порядок решения неважен. Отсортируем заданные числа по возрастанию и посчитаем динамику d[i][j][k] - наименьшее пенальти, которое можно получить, решив первые i задач, из них j - после Нового года, причем последняя задача после Нового года решена в момент k. Заметим, что по (i, j, k) однозначно определяется количество задач, решенных до Нового года, и суммарное время на их решение. После подсчета динамики вспомним про задачу, которая решалась непосредственно в 0:00 (и которая не участвовала при подсчете динамики). Переберем момент времени до Нового года, когда началось ее решение, и учтем остальные задачи при помощи посчитанной динамики.
Сначала научимся решать подзадачу для одного яруса: составить гирлянду длины s из лампочек ровно k цветов, так чтобы никакие две лампочки одного цвета не шли подряд. При этом варианты, отличающиеся порядком цветов, пока считаем одинаковыми (при необходимости мы всегда успеем домножить на k!). Решение подзадачи нам нужно лишь для k ≤ s ≤ 5000, поэтому считаем динамику за O(s2):
a[s][k] = a[s-1][k-1] + a[s-1][k] * (k -1).
Далее, посчитаем динамику d[i][j] - количество способов сделать гирлянду для первых i ярусов (с учетом правил), чтобы на i-м ярусе было ровно j различных цветов. Состояний будет порядка L (общей длины гирлянды), потому что на каждом ярусе различных цветов не больше, чем длина яруса: j ≤ li (!). Переходы тоже можно делать за O(L), если учесть тот факт, что множества цветов различной мощности различны (!!). Действительно, положим d[i][j] = Amj * a[l[i]][j] * (сумму всех d[i-1][k]), а потом вычтем варианты, при которых множества на i-м и (i-1)-м ярусах получаются одинаковыми. Количества размещений Amj = m(m - 1)... (m - j + 1) можно предпосчитать, так они нужны только для j до 5000.
Таким образом, авторское решение работает за O(L + s2) (L ≤ 107, s ≤ 5000), причем не использует деления (только операции умножения и сложения по заданному модулю).
Начнем с того, как выполнить проверку кандидата на центр симметрии
(xc, yc). Рассмотрим все точки, симметричные относительно него для
(xi, yi). Они имеют вид
(2xc - xi, 2yc - yi). Необходимо выяснить, правда ли, что все они, кроме не более
k точек, содержатся в множестве
{(xi, yi)}. Это можно сделать за
бинарным поиском (предварительно отсортировав заданное множество). Однако существует более быстрый способ проверки за
O(n). Заметим, что если изначально точки
(xi, yi) были упорядочены, скажем, по возрастанию x, а при равенстве x - по возрастанию y, то точки вида
(2xc - xi, 2yc - yi) получатся в порядке, обратном порядку сортировки. Причем вне зависимости от центра
(xc, yc). Поэтому если проверять точки
(2xc - xi, 2yc - yi) по порядку, можно просто двигать указатель с конца в отсортированном массиве
(xi, yi).
Из предыдущих рассуждений следует, что если множество имеет центр симметрии, то для первой точки (в порядке сортировки) парная n-я, для второй - (n-1)-я, и т.д. Учитывая, что k точек могут не иметь парных, переберем первые (k+1) точку с начала массива и (k+1) с конца. Для каждый пары таких точек найдем середину соединяющего их отрезка и выполним ее проверку за O(n). Асимптотика решения - O(nk2).
В заключение пару слов о порядке сложности задач. Сложность задачи - величина субъективная. Особенно когда приходится сравнивать идейную задачу с простой реализацией и реализационную задачу почти без идеи. В результате у разных участников получились разные
списки предпочтений. Не могу не признать, что порядок, выбранный при подготовке контеста, оказался не совсем адекватен по отношению, например, к
количеству решивших задачи, а тем более мог не понравиться кому-то лично. Тем не менее скажу пару слов в его поддержку. А именно, каким принципами мы руководствовались, когда его выбирали.
Количество баллов за задачу - это в первую очередь ее "цена". Умение решать идейные задачи, ИМХО, должно цениться выше, чем умение решать реализационные. Потому что реализацию на уровне задачи B может научиться писать каждый. А вот идея с сортировкой по задаче D на моих глазах не пришла нескольким сильным и опытным участникам. Что касается порядка задач - никто не заставляет вас решать задачи строго по порядку. Ничего плохого нет, если вам быстро приходит идея по задачам C-D, и вы решаете их раньше B и получаете много баллов. Многие так и поступили. Тем более есть текущее положение участников, которым можно руководствоваться при выборе задач.