9. Решающий удар
Для определения вероятности посчитаем динамику
v[n][d] — количество исходов при бросании n игральных костей,
при которых сумма результатов равна d.
База динамики
Для первой кости и каждого из исходов 1 <= d_roll <= f
v[1][d_roll] = 1.
Переход динамики
Уже бросили (n - 1) кость и сумма результатов равна d,
бросаем ещё одну кость и выбрасываем на ней d_roll, тогда
v[n][d + d_roll] увеличивается на v[n - 1][d].
При добавлении очередной кости суммируем по всем d и d_roll.
Количество нужных нам исходов получаем суммой
S = sum v[n][d], max(1, D - m) <= d <= n * f.
Итоговая вероятность равна
S / f^n.
7. Планировщик
Пусть X[i] = P[i] + T[i]. В задаче нужно выбирать среди N значений X[i] минимальное — для этого отлично подойдёт бинарная куча. Кроме того, нужно на каждой итерации прибавлять единичку ко всем X[i] (кроме одного). Чтобы этого не делать, давайте договоримся, что будем хранить в программе Y[i] = X[i] — t, где t — сколько секунд прошло с начала работы планировщика. В этом случае прибавление единички ко всем X[i] происходит автоматически благодаря тому, что мы увеличиваем t после каждой итерации. Решение заключается в том, чтобы хранить и поддерживать Y[i] для всех процессов в бинарной куче. На каждой итерации нужно выбрать процесс с минимальным значением Y[i], и присвоить ему Y[i] := P[i] — (t+1), обновив его положение в куче. Чтобы среди процессов с равным приоритетом выбирался процесс с минимальным номером, можно хранить в куче на максимум пары (Y[i], -i) с лексикографическим сравнением. Разумеется, свою бинарную кучу писать не обязательно. В C++ для этого есть push_heap/pop_heap, priority_queue и set, а Java есть TreeSet.
5. Леспромхоз
Область, в которой может находиться машина, чтобы захватить конкретное дерево — это кольцо с радиусом от H — R до H + R (центр в P). Нужно найти точку, которая попадает в максимальное количество колец. Легко заметить, что оптимальный ответ будет среди таких точек: 1) точки пересечения граничных окружностей 2) по одной произвольной точке на каждой окружности Доказывается так: рассмотрим оптимальную точку, если она не такая, будем двигать её или куда угодно, или по окружности, и получим такую точку с кратностью не хуже. Всего O(N^2) пробных точек, каждая проверяется влоб за O(N). Получаем решение за O(N^3).
3. Найти радистку
Сделаем два запроса: ? -10000 -10000 1 0 ? -10000 -10000 0 1 Поскольку координаты цели небольше 1000 по модулю, цель точно расположена строго между ними. Отношение уровня сигнала этих двух запросов даёт тангенс угла между осью координат и направлением на цель. Затем можно сделать аналогичные два запроса из точки (-10000, 10000), например. В результате получится два луча, которые гарантированно не параллельны. Находим точку пересечения и округляем — это и будет положение цели. Хватает 5 запросов, считая последний запрос на попадание в цель.
6. Кеширование приближений
Прежде всего, для каждой операции вместо данного tol посчитаем L — минимальный размер подходящего приближения:
L = S * pow(1/tol, 0.25)
Теперь получается, что для операции нужно иметь приближение размера M >= L, при этом тратится время C * M + D.
На построение приближения размера M тратится A * M + B времени — сложных формул больше нет.
В варианте 1, когда кеширование отключено, для каждой операции надо строить приближение заданного размера L.
Что-то более точное строить смысла нет — всё равно на выброс.
Тогда ответ равен:
ans = sum { (A * L[i] + B) + (C[i] * L[i] + D[i]) }
i=1..n
В варианте 2 можно хранить только одну кривую.
Нужно разбить все n операций на отрезки, такие что на каждом отрезке используется своё приближение, а между отрезками приближение перестраивается.
Запишем ДП:
R[i] — минимальные затраты времени, чтобы а) покрыть первые i операций описанными выше "отрезками"
(0 <= i <= n) б) выполнить первые i операций, так что перед i-ой операции приближение будет выброшено/перестроено
Рекуррентная формула пишется по достраиванию последнего "отрезка" от R[j] до R[i].
Очевидно, для него надо брать допустимое приближение минимального размера Hij:
Hij = max L[k]
k=j..i-1
При этом на построение этого приближения и на выполнение с ним всех операций на отрезке потребуется:
Tij = (A * Hij + B) + sum (C[k] * Hij + D[k])
k=j..i-1
С этими значениями общая формула записывается так:
R[i] = min (R[j] + Tij)
j < i
Значения Hij и Tij можно довычислять за O(1) внутри цикла по j.
Получается решение за O(N^2) времени и с O(N) памяти.
В варианте 3 можно хранить сколько угодно приближений в кеше.
Легко понять, что в таких условиях можно построить все приближения заранее, а потом для каждой операции выбирать самое маленькое подходящее.
Следовательно, от порядка операций ничего не зависит: давайте отсортируем их по возрастанию размера L[i].
Теперь для первых операций используется первое приближение, затем в какой-то момент переключаемся на второе, затем на третье, и т.д.
То есть по сути после сортировки в кеше можно хранить только одно приближение, а значит задача свелась к предыдущей.
Запускаем в точности динамику из варианта 2, только после предварительной сортировки по L[i].
В ответ выводим, что все построенные приближения надо построить сразу, до первой же операции.
4. Код Морзе
Разобъём сигнал на элементы — отрезки одинаковых значений. Будем решать динамикой, читая элементы по очереди. Состояния динамики: R[k] — минимальное количество ошибок при расшифровке префикса из k элементов в полные слова Переход — выбрать любое слово в словаре и добавить его. При этом надо наложить закодированный вид слова на продолжение сигнала и посчитать количество ошибок. Т.к. каждое слово из каждого состояния обрабатывается примерно за его длину, получаем: Память: O(N) (N — количество элементов) Время: O(N D) (D — суммарный размер словаря) На самом деле, легко заметить, что если сигнал можно расшифровать, то количество ошибок при любом варианте расшифровке получается одинаковое. Так что существенная часть задачи — это выбор лекс. минимального варианта текста. Чтобы его найти, можно традиционно запустить динамику в обратном направлении: R[k] — минимальное количество ошибок при расшифровке суффикса, начинающегося с k-ого элемента, в полные слова Переходы надо делать в сторону уменьшения k, и для каждого состояния сохранять лекс. минимальное слово, по которому в него пришли. Тогда обратный ход восстановит лексикографически минимальный ответ. Стоит заметить, что на многих тестах в этой задаче отлично работают всякие переборы с отсечениями. Можно построить класс тестов, которые эквивалентны задаче о рюкзаке, ставя четыре минуса между одинаковыми буквами и задавая слова из той же буквы разной длины. На таких тестах переборы работают плохо, так что хочется верить, что исчезающе мало переборов получило Accepted =)
8. Текстовый редактор
Если разобраться в механике процесса, то получается, что план должен состоять из 1) перемещений вверх/вниз и 2) переноса куска текста.
При переносе определяется, до какой позиции от текущий надо выделить кусок, и в какое именно место вставить.
Поскольку N довольно маленькое, можно решить задачу "влоб".
Составим граф состояний и переходов.
Состояние — это порядок строк текста плюс текущее положение курсора. Всего (N+1)! состояний (N = 8 -> 362880 штук).
Переходов из каждого состояния порядка O(N^2) — нужно перебрать две позиции. (N = 8 -> примерно 30 штук)
Далее на этом графе можно запустить алгоритм Дейкстры с кучей, получив решение за O((N+1)! * N^2 * N).
Концептуальных сложностей в этом нет, однако в задаче довольно жёсткие требования по скорости работы.
Поэтому нужно применить следующие оптимизации:
1) Вместо того, чтобы складывать все состояния в map/dictionary, можно их все честно закодировать номерами от 0 до (N+1)!-1.
2) Поскольку все расстояния и тайминги очень маленькие, то в алгоритме Дейкстры вместо кучи можно использовать набор списков.
То есть для каждого числа k = 0..5000 хранить список всех вершин v, у которых D[v] = k.
3) Порядок строк не влияет на структуру переноса, поэтому можно предподсчитать все переносы для каждого положения курсора.
Получится O(N^3) переходов, для каждого можно заранее сохранить перестановку строк, стоимость, новое положение курсора.
В принципе, можно дополнительно оптимизировать алгоритм с помощью эвристики A*, хотя для получения Accepted это было НЕ обязательно.
Для этого нужно построить функцию оценки снизу расстояния до конечного состояния.
Пусть D элементов находятся не на своём месте.
Тогда необходимо сделать как минимум D нажатий клавиш вверх или вниз, чтобы "замести" эти строки — иначе не получится их изменить.
Теперь найдём "разрезы" — такие положения, что строка снизу и строка сверху в конечном состоянии НЕ должны тоже идти подряд в том же порядке.
Каждое наше перемещение режет текст в трёх местах и сшивает по-другому, а значит устраняет максимум три разреза.
Поэтому если есть K разрезов, то нужно как минимум roundup(K/3) перемещений, в каждом из них нужно нажать по одному разу все клавиши/комбинации кроме вверх/вниз.
Получается оценка:
H(v) = D * min(Tup, Tdown) + roundup(K/3) * (Tshpr + Tshrel + Tctrlx + Tctrlv)
Можно показать, что эта оценка монотонная, то есть с ней алгоритм A* эквивалентен алгоритму Дейкстры с потенциалами, и все модифицированные веса неотрицательные.
2. Антиталия
Будем решать задачу методом движущейся плоскости: будем считать, Z-координату сечения "временем", и смотреть, как изменяется сечение. В сечении всегда получается набор контуров (внешних/внутренних), ограничивающих плоскую область (или несколько плоских областей). По мере увеливения Z структура контуров сохраняется, а точки в контурах движутся с некоторой скоростью — пока секущая плоскость не пройдёт через какую-нибудь вершину триангуляции. Прохождение плоскости через вершину будем считать событием и обрабатывать особо. В отличие от простых задач, где ответ всегда совпадает с каким-нибудь событием, в этой задаче оптимальное сечение может произойти между событиями (см. пример 2). Заметим, что с течением времени (t = Z) каждая точка контура в сечении движется с постоянным вектором скорости, то есть координаты точек линейно зависят от времени. Поскольку площадь контура считается как полусумма cross(P[i], P[i+1])/2, то получается, что площадь сечения зависит от времени квадратично. Если для конкретного интервала между соседними событиями посчитать площадь как квадратичную функцию от Z, то найти её максимум на интервале будет легко: надо лишь проверить значение в начале и в конце, а также в вершине параболы, если она находится внутри интервала. К сожалению, отслеживать контуры в сечении очень сложно: контуры возникают, объединяются, разделяются и т.п. На самом деле, это и не нужно: вклад каждого отрезка сечения в площадь сечения никак не зависит от окружающих объектов. Действительно, каждый отрезок P->Q сечения добавляет cross(P, Q)/2 в общую площадь — главное верно определить направление отрезка, т.к. от этого зависит знак площади. Оказывается, если сторона треугольника пересекает плоскость сверху вниз (т.е. Z убывает), тогда точка пересечения будет началом отрезка сечения, порождённого этим треугольником. Другая сторона треугольника, которая пересекает плоскость снизу вверх (Z возврастает), будет концом этого отрезка. Третья сторона в сечении отсутствует: они либо полностью сверху, либо полностью снизу плоскости. Разумеется, здесь подразумевается, что стороны направлены в порядке обхода, указанном в файле. Таким образом, получается довольно простое решение. Выпишем все события (т.е. вершины сетки) в один большой массив, отсортируем их по времени. Далее обрабатываем события по порядку, все одновременные события обрабатываем одной группой. Сначала для всех треугольников, инцидентных всем вершинам в текущей плоскости, "выключаем" старый отрезок, а затем для всех этих же треугольников считаем и "включаем" новый отрезок. Вклад каждого отрезка-треугольника в площадь лучше хранить в массиве, тогда выключение — это просто зануление соотв. элемента этого массива. При включении нужно представить, что секущая плоскость чуть выше рассматриваемой плоскости, понять, как устроен отрезок сечения, и посчитать векторное произведение движущихся точек. Разумеется, если треугольник/отрезок уже включен, то включать его повторно не надо, чтобы не учесть его вклад в площадь дважды. Текущую площадь как квадратичную функцию можно хранить в глобальной переменной: при выключении отрезка вычитать его старую функцию, а при включении добавлять новую функцию. Если предподсчитать списки инцидентных вершинам треугольников заранее, то весь алгоритм будет работать за O(N log N). Одна из проблем этой задачи — точность при работе с квадратичными функциями (коэффициенты которых никак не целые). При желании почти любое решение можно завалить по точности, сделав соответствующий тест. При подготовке задачи все проблемные тесты были выброшены, а требование точности было выставлено так, чтобы все правильные решения проходили с запасом (все они используют тип double). Тем не менее, есть ряд способов кардинально улучшить точность решения в разных ситуациях (ни один из них НЕ был нужен, чтобы получить Accepted): 1) Хранить квадратичные функции для треугольников не в обычном массиве, а в дереве отрезков на сумму, при изменении честно пересчитывая все узлы до корня. Это позволяет полностью избежать накопления погрешности, а кроме того снижает погрешность суммирования в целом (см. https://en.wikipedia.org/wiki/Pairwise_summation). 2) Вычислять для отрезка cross(P, Q-P) вместо cross(P, Q): помогает для тонких тел вдали от начала координат по X/Y. 3) Вычислять квадратичные функции не от переменной Z, а от смещения (Z — O), где O — это например Z-координата вершины треугольника, при рассмотрении которой вычислялась эта функция. Это сильно повышает устойчивость представления квадратичных функций для коротких по Z треугольников на большом расстоянии от Z == 0. Правда при сложении функций с разными O в дереве отрезков нужно делать дополнительную конвертацию.
