Блог пользователя ashmelev

Автор ashmelev, история, 6 лет назад, По-русски

991A - If at first you don't succeed...

Разбор

Решение1

Решение2

991B - Getting an A

Разбор

Решение

991C - Candies

Разбор

Решение

991D - Bishwock

Разбор

Решение1

Решение2

991E - Bus Number

Разбор

Решение

991F - Concise and clear

Разбор

Решение

Полный текст и комментарии »

Разбор задач Codeforces Round 491 (Div. 2)
  • Проголосовать: нравится
  • +91
  • Проголосовать: не нравится

Автор ashmelev, история, 6 лет назад, По-русски

Привет!

В субботу 23 июня в 18:35 (Московское время) начнется Codeforces Round #491 (Div.2). Раунд будет рейтинговым для участников с рейтингом менее 2100, остальные участники могут решать задачи вне конкурса.

Раунд во многом пересекается с задачами олимпиады по программированию ННГУ 2018 года. Если вы принимали участие в олимпиаде или дорешивали задачи, просьба не участвовать в раунде.

В задачах раунда вам нужно будет помочь студенту Васе справиться с трудностями, вызванными окончанием учебного года. Всего будет предложено 6 задач и 2 часа на их решение. Если же вы решите все задачи за 25 минут, то успеете посмотреть второй тайм матча Южная Корея — Мексика на чемпионате мира FIFA.

Разбалловка немного нестандартная: 500-1000-1250-1500-2000-2750

Выражаю максимальную благодарность Михаилу MikeMirzayanov Мирзаянову за всем известные платформы; Николаю KAN Калинину — за помощь в подготовке задач и координацию раунда; Михаилу mike_live Кривоносову, Алексею Livace Илюхову, Никите FalseMirror Босову, Андрею GreenGrape Райскому и Алексею Aleks5d Упирвицкому — за тестирование задач; Арсению arsor Сорокину — за перевод условий. А всем участникам желаю удачи на раунде!

UPD: Раунд завершен, всем спасибо за участие!

UPD: Поздравляем победителей!

Div. 1:

  1. nuip
  2. krijgertje
  3. qoo2p5
  4. hohomu
  5. neal

Div. 2:

  1. King — решил все задачи, отличный результат!
  2. Daniar
  3. Saidjamol
  4. shoemakerjo
  5. Toki_Time-Tinker

UPD: Опубликован разбор задач

Полный текст и комментарии »

  • Проголосовать: нравится
  • +380
  • Проголосовать: не нравится

Автор ashmelev, 9 лет назад, По-русски

Всем привет! Может быть, эта тема уже обсуждалась, но по запросу "random" ничего похожего на Codeforces не нашел.

Предыстория. Хотели с Сашей (demon1999) изучить декартово дерево. Для инициализации приоритетов рекомендуется использовать случайные числа, чтобы высота дерева не была очень большой. Соответственно, надо эти числа как-то получить. Я совсем не разбираюсь в структурах данных, поэтому не задумывался, насколько плохо будет дереву (и будет ли), если приоритеты нескольких вершин будут одинаковыми. Поэтому на всякий случай хотелось сделать их попарно различными (чего не гарантирует простое использование rand() при создании очередной вершины). Предложил следующий, "надежный" и "проверенный" метод — создать массив из N чисел, инициализировать его числами от 0 до (N-1) соответственно, применить к нему random_shuffle — и мы получим N различных ключей в случайном порядке.

История. Саша стала сдавать задачи и на практике оказалось, что в нескольких задачах такой подход достаточно стабильно приводит к вердикту Time Limit Exceeded, в то время как простейшая инициализация pr=rand() получала Accepted. Стало очень интересно, почему так происходит, да и вообще STL не склонен быть причиной каких-либо ошибок. После несложных исследований оказалось, что (возможно, не это причина TLE, но тем не менее) random_shuffle перемешивает массив не совсем случайным образом.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +437
  • Проголосовать: не нравится

Автор ashmelev, 12 лет назад, По-русски

Задача 175F - Gnomes of Might and Magic

Построим граф, вершины которого будут соответствовать замкам, а ребра — дорогам. Заметим, что степень каждой вершины в графе не превосходит 4, значит, количество ребер E <= 2 * N.

Для решения задачи научимся обрабатывать каждый запрос за время в среднем O(_log_(_N_)). Рассмотрим запрос на нахождение числа гномов, уничтоженных Миссией Смерти. Если принять за вес ребра количество гномов на соответствующей дороге, то нам необходимо найти кратчайший путь между двумя вершинами, а среди них — минимальный по числу ребер. Таким образом, путь характеризуется двумя числами — G и R — количество гномов и дорог (лексикографическую минимальность пока учитывать не будем). Одно ребро между вершинами u и v имеет характеристики (_C_(_u_,_v_), 1), где C(_u_,_v_) — количество гномов на ребре (_u_,_v_). Рассмотрим две вершины s и t, между которыми мы ищем путь. Кратчайший путь между ними может иметь один из двух видов:

  • путь по Обходу Зла, если обе вершины находятся на одном Обходе
  • путь вида s -> g1 -> g2 -> t, где g1 и g2 — вершины на Пути Добра, причем g1 и s лежат на одном Обходе, g2 и t лежат на одном обходе (некоторые из данных 4 вершин могут совпадать).

Значит, достаточно научиться быстро определять кратчайший путь между вершинами e1 и e2 по Обходу Зла и между вершинами g1 и g2 по Пути Добра. Для нахождения расстояния между вершинами по Обходу Зла заведем на ребрах каждого Обхода дерево отрезков etree[i], поддерживающее операции изменения элемента и нахождения суммы на интервале. Для каждой вершины сохраним номер Обхода Зла, на котором она лежит, и ее порядковый номер на данном Обходе (при реализации стоит аккуратно обрабатывать случаи с вершинами Пути Добра, поскольку они принадлежат двум Обходам). Тем самым, расстояние между двумя вершинами одного Обхода равно сумме весов ребер соответствующего дерева на интервале с границами, равными порядковым номерам вершин. Аналогично, заведем дерево отрезков gtree и для Пути Добра, разрезав его по первой вершине (для путей, в которых она является внутренней, будем делать два запроса). При этом для каждой пары соседних вершин Пути будем хранить в дереве минимальное из расстояний – расстояние по ребру Пути Добра или расстояние по Обходу Зла. Таким образом, для любых двух вершин Пути Добра, соответствующий запрос к дереву вернет длину (пару чисел) кратчайшего из всех путей между этими вершинами. Данная структура позволяет находить кратчайшее расстояние между двумя произвольными вершинами Пути или одного Обхода за O(_log_(_N_)). Изначально для каждой пары соседних вершин Пути Добра нужно обновить соответствующий элемент дерева значением (_0_, 1).

Теперь рассмотрим запрос на добавление одного гнома на ребро. Для быстрой обработки этого запроса нам придется дополнительно хранить количество гномов gsum[i] на каждой дороге Пути Добра и суммарное число гномов esum[i] на каждом Обходе Зла. Если гном встал на ребро i Пути, то увеличим gsum[i] на 1. Аналогично, если гном встал на ребро Обхода i, то увеличим esum[i] на 1, а так же обновим соответствующее ребру значение в дереве etree[i]. После любого из этих действий потребуется так же записать в дерево gtree новое значение кратчайшего пути между соответствующими соседними вершинами, поскольку оно могло измениться. Заметим, что при удалении гномов с ребра можно проделать обратные операции с той же асимптотикой. Таким образом, запрос на изменение количество гномов на ребре можно обработать за O(_log_(_N_)).

Далее научимся находить кратчайший путь между двумя произвольными вершинами s и t. Создадим вектор вершин Пути Добра sg, до которых можно добраться из s по Обходу Зла, на котором она лежит (соответственно, в sg будет одна или две вершины). Аналогично, вектор tg — вершины Пути Добра, до которых можно добраться из t по Обходу Зла. Рассмотрим объединение векторов tsg = sg + tg. Для каждой вершины u объединения найдем вершину v1, которая первая среди вершин tsg встретится на пути из u, если двигаться по Пути Добра в сторону увеличения индексов вершин (т.е. в том порядке, в котором вершины Пути даны во входных данных). Аналогично, v2 – первая вершина на противоположном направлении. Добавим в список смежности вершины u найденные вершины v1 и v2 вместе с расстояниями до них. Кроме того, так же найдем ребра (расстояния по Обходам Зла) из s в вершины вектора sg, из вершин tg – в вершину t. Если вершины s и t лежат на одном Обходе Зла (и обе не лежат не Пути Добра), то добавим еще прямое ребро из s в t, соответствующее пути по Обходу Зла. Таким образом, мы получили граф, состоящий не более чем из 6 вершин и не более чем из 13 ребер. Запустим алгоритм Дейкстры на этом графе для нахождения кратчайшего пути из s в t. Заметим, что пути исходного графа, соответствующие ребрам нового графа, не пересекаются по внутренним вершинам (кроме, возможно, прямого ребра из s в t). Поэтому для определения лексикографической минимальности достаточно знать только первую внутреннюю вершину на пути, соответствующем какому-либо ребру. Тогда можно, например, добавить еще один параметр для каждого пути нового графа – вектор индексов первых вершин исходного графа при переходах по ребрам нового графа. В этом случае 3 параметра (число гномов, число ребер, вектор индексов) однозначно определят оптимальный путь, по которому будет двигаться Миссия Смерти.

Далее нужно вывести ответ и научиться обрабатывать уничтожение гномов на пути. Восстановим вершины в оптимальном пути. Ребро между каждой парой соседних вершин представляет собой либо путь по Обходу Зла, либо путь между двумя вершинами Пути Добра. Для быстрого поиска гномов, находящихся на Обходах Зла, заведем для каждого Обхода мультисет eset[i] из индексов ребер этого обхода, на которых находятся гномы. Тогда при добавлении гнома на ребро необходимо будет добавить соответствующий индекс в мультисет Обхода. Теперь для удаления гномов с Обхода Зла i, находящихся между ребрами l и r, достаточно найти итератор первого гнома, использовав eset[i]._lower_bound_(_l_) и итерировать, сохраняя полученные позиции гномов в список, пока очередное значение не превысит r. После этого необходимо удалить всех гномов, попавших в список при помощи описанной выше процедуры (аналогично добавлению). Для обработки путей между двумя вершинами Пути Добра, заведем сет gset индексов на Пути, таких что между соседними вершинами, соответствующими индексу, не существует пути, не содержащим гномов. Для поддержания сета необходимо при каждом изменении (добавлении/удалении) гнома добавить проверку: если минимальное расстояние (соответствующее значению в дереве gtree) стало равно 0 (по количеству гномов), то нужно удалить соответствующий индекс из gset, в противном случае – добавить. Тогда, проделав аналогичную процедуру (вызвав gset._lower_bound_ и проитерировав необходимое число раз), мы получим список индексов вершин, проходя через которые мы будем должны уничтожить хотя бы одного гнома на пути к следующей вершине Пути Добра (понятно, что пары вершин, между которыми есть путь, не содержащий гномов, нас не интересуют, ибо Миссия Смерти пройдет по нему, никого не уничтожив). Рассмотрим индекс i этого списка. Если для соответствующей вершины оптимальный путь в следующую вершину Пути Добра лежит через Обход Зла, то есть esum[i] < gsum[i], то необходимо удалить всех гномов с этого Обхода, алгоритмом, описанным выше. В противном случае, достаточно задать gsum[i] = 0 и обновить соответствующее значение в дереве отрезков Пути gtree.

Таким образом, одного гнома с пути, по которому прошла Миссия Смерти, можно удалить за O(_log_(_N_)). Поскольку количество удалений гномов не превосходит количества добавленных гномов (то есть не более Q – количество запросов), то амортизационная сложность одного запроса на обработку Миссии Смерти есть так же O(_log_(_N_)). Итого, общая сложность алгоритма есть O(_log_(_N_) * Q).

Полный текст и комментарии »

Разбор задач Codeforces Round 115
  • Проголосовать: нравится
  • +46
  • Проголосовать: не нравится

Автор ashmelev, 12 лет назад, По-русски

Задача 175A - Robot Bicorn Attack

Переберем все возможные разбиения данной строки на 3 подстроки (например, перебрав пару индексов – конец первой подстроки и конец второй подстроки). Если при разбиении все три подстроки удовлетворяют ограничениям (не имеют ведущих нулей и соответствующие им числа не превосходят 1000000), то пытаемся обновить текущей ответ суммой чисел данных подстрок. Всего количество разбиений O(N^2), где N – длина исходной строки. Проверка одного разбиения осуществляется за O(N)

Задача 175B - Plane of Tanks: Pro

Для решения необходимо промоделировать действия описанные в условии. Для каждого игрока оставим наилучший результат и посчитаем общее количество игроков N. Далее для каждого игрока найдем количество игроков C, результат которых не лучше наилучшего результата рассматриваемого игрока (это можно сделать простым циклом по всем игрокам). Далее необходимо определить его категорию по числам C и N. Для избежания проблем с точностью можно воспользоваться следующим подходом:

  • если C * 100 >= N * 99, то игрок относится к категории "pro"
  • если C * 100 >= N * 90, то игрок — "hardcore"
  • если C * 100 >= N * 80, то игрок — "average"
  • если C * 100 >= N * 50, то игрок — "random"

В противном случае игрок "noob".

Задача 175C - Geometry Horse

Очевидно, что фигуры следует уничтожать в порядке возрастания их стоимости. Отсортируем типы фигур в порядке возрастания стоимости. Создадим два указателя – позиция i в массиве P (текущий множитель) и позиция j в массиве типов фигур. При этом будем поддерживать текущий ответ и количество фигур G, которое необходимо уничтожить для перехода к следующему множителю. Если на очередном шаге количество фигур F текущего типа не превосходит G, то к ответу следует прибавить F * (i + 1) * Сj, G уменьшить на F, а указатель j увеличить на 1. В противном случае, к ответу необходимо прибавить G * (i + 1) * Cj, F уменьшить на G, указатель i увеличить на 1 и задать G = Pi – P(i-1). Такие итерации нужно продолжать, пока мы не просмотрим весь массив типов фигур.

Задача 175D - Plane of Tanks: Duel

Сначала необходимо определить исход битвы, если хотя бы одна из вероятностей непробития равна 100%. Если Вася не пробивает вражеский танк с вероятностью 100%, то ответ на задачу – 0. В противном случае, если Васин танк не пробивают с вероятностью 100%, то ответ на задачу – 1. Далее будем считать, что вероятности непробития не превосходят 99%. Можно проверить, что вероятность того, что танк останется живым после D = 5000 выстрелов по нему, меньше 10^-6 (для любых значений урона, пробиваемости и количества очков жизни). Для каждого из двух танков посчитаем следующую динамику dp[i][j] — вероятность того, что у танка останется j очков жизни после i выстрелов по нему. dp[0][hp] = 1, где hp – начальное количество очков жизни танка. Далее, для пересчета строки dp[i+1] достаточно для каждого значения j в строке dp[i] перебрать урон, который нанесет (i+1)-й снаряд (с учетом возможного непробития) и обновить соответствующее значение строки (i+1):

dp[i + 1][max(0, j – x)] += dp[i][j] * (1 – p) / (r – l + 1)

где p – вероятность непробития, x – потенциальный урон снаряда. Пусть dpv – полученная таблица для танка Васи, dpe – для танка врага.Теперь можно найти вероятность, что танк врага будет убит i-м выстрелом танка Васи: pk[i] = dpe[i][0] – dpe[i-1][0]. Заметим, что победы Васи происходят следующим образом: Вася сделал (K — 1) выстрелов и не убил вражеский танк, при этом не умер и сам. После чего Вася произвел K-й выстрел и уничтожил врага. Переберем K и посчитаем вероятность победы Васи K-м выстрелом. Для этого найдем, сколько выстрелов T успеет произвести враг прежде чем Вася выстрелит K-й раз (здесь нам единственный раз в решении понадобится скорострельность орудий):

T = ((K – 1) * dtv + dte - 1) / dte

где dtv – время перезарядки танка Васи, dte – время перезарядки врага. Тогда вероятность победы будет равна (1 – dpv[T][0]) * pk[K]. Просуммировав такие вероятности для K от 1 до D мы получим ответ. Вычислительная сложность алгоритма при этом есть O(D * hp * (r – l)).

Задача 175E - Power Defence

Заметим, что если отразить позицию башню относительно прямой OX, то интервал на пути движения монстра, на котором будет действовать башня, не изменится. Таким образом, можно считать, что башни разрешено строить в точках (_x_, 1), не более двух в одной точке. Далее заметим, что если существует такая точка X, что как слева, так и справа от нее располжены башни, а в самой точке X башен нет, то абсциссы всех «правых» башен можно уменьшить на 1 и от этого ответ не ухудшится. Аналогично, можно считать, что не существует двух соседних точек, в каждой из которых стоит ровно по одной башне. Теперь легко проверить, что для построения оптимального решения нам достаточно 13 подряд идущих целых точек. Переберем позиции замедляющих башен. В худшем случае, способов расставить замедляющие башни на 13 точках будет порядка 200000. Пусть мы зафиксировали некоторое расположение замедляющих башен. Для каждой из оставшихся свободных точек (точки, в которые можно поставить две башни, раздваиваем) посчитаем, какой урон нанесет огненная или электрическая башня, расположенная в этой точке, и сохраним полученные числа в массиве d (_d_[k].f и d[k].e – урон огненной и электрической башнями в точке k соответственно). Полученный массив пар значений отсортируем в порядке убывания первого значения d[k].f. Тогда оптимальное расположение оставшихся башен можно найти при помощи динамического программирования. Обозначим за dp[i][j] – наибольший урон, который можно получить, если у нас осталось i огненных башен и j электрических. Обозначим за p следующую величину p = cf – i + ce – j – количество башен, которое мы уже расставили при данном состоянии динамики. Заметим, что если i = 0, то мы использовали первые p значений массива d и ответом будет сумма наибольших j элементов d[k].e, начиная с индекса p. Иначе, мы либо ставим одну огненную башню, либо одну электрическую в позицию p. Не ставить башню в позицию p невыгодно в силу уменьшения значения d[p].f. Тогда получаем:

dp[i][j] += max(dp[i - 1][j] + d[p].f, d[i][j – 1] + d[p].e)

Ответом при данном расположении будет значение dp[cf][ce], которое вычисляется за время O(cf * ce * log(ce))

Замечание1: перебор можно сократить почти в 2 раза в силу того, что любые две симметричные друг другу расстановки эквивалентны между собой и дадут одинаковый ответ, однако, при данных ограничениях эта оптимизация не является необходимой

Замечание2: формула снижения скорости монстра 1 / (K + 1) позволяет легко посчитать урон от башни при фиксированных позициях замедляющих башен – замедляющие башни можно рассматривать независимо друг от друга

Полный текст и комментарии »

Разбор задач Codeforces Round 115
  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски

Вот и наступил последний день нашего пребывания в Токио. Собственно, на этот день и был запланирован гуглоконтест, а так же все прилагающиеся к нему мероприятия: разбор задач, награждение, пьянка торжественный ужин.


Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски

(приношу извинения за большие перерывы во времени между написанием частей, для тех, кто забыл о чем речь или вообще не в курсе, о чем сей пост - вот ссылки на предыдущие части: первая, вторая)

На третий день нашего путешествия нужно уже было переселяться в отель IBIS Roppongi, предложенный гуглом для проживания участников. Отель выглядел очень даже неплохо:

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски

На второй день пребывания в Токио мы, следуя пути самурая плану Милы-сан, отправились на остров Одайба. Главной целью поездки был "музей будущего" Мирайкан:


Полный текст и комментарии »

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски

29 июля в Токио прошел финал соревнования Google Code Jam. Каким-то непонятным образом в этом году мне удалось попасть в финал и посетить столицу Японии. Также на онсайт попал мой однокомандник Владислав Епифанов (vepifanov). Кроме того, мы договорились с саратовскими друзьями - Наташей Бондаренко (natalia) и Артемом Раховым (RAD) о совместном времяпрепровождении. Более того, по счастливому стечению обстоятельств, моя женщина, Мила Голубева (iberia), на данный момент проживает всё в том же Токио и великодушно согласилась сопровождать нас в этом путешествии. Таким образом, русская компания для обсуждения насущных проблем бытия подобралась вполне достойная:

  

Далее речь в этом посте пойдет не о самом соревновании, а о некоторых достопримечательностях Токио. Мы решили приехать на онсайт чуть раньше и успели посетить пару интересных мест, проведя в Японии 4 дня. 

Полный текст и комментарии »

  • Проголосовать: нравится
  • +83
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски

Задача D.

Разобьем граф на компоненты связности (провинции). Далее будем рассматривать только граф на этих компонентах, то есть каждой провинции мы поставим в соответствие вершину нового графа. Пусть всего имеется n провинций. Изначально граф пустой, так как между провинциями дорог нет. При этом для каждой провинции мы имеем ограничение на число тоннелей, которые можно построить из этой провинции: ki = min(k, ci), где ci – количество городов, изначально содержавшихся в провинции (компоненте) i. Полученный граф провинций требуется сделать связным за счет постройки тоннелей и дорог. При k = 1 получаем, что если после постройки дорог у нас осталось хотя бы 3 компоненты связности, то хотя бы из одной из них придется провести 2 тоннеля, что запрещено. Значит, нам надо будет провести хотя бы n – 2 дороги, чтобы осталось не более 2 компонент связности.

Далее будем считать, что k >= 2. Посчитаем, какое наибольшее количество тоннелей мы можем построить. Пусть s – сумма всех чисел ki. Очевидно, мы не сможем построить больше, чем s / 2 тоннелей, поскольку каждый тоннель соединяет 2 провинции. Верно следующее утверждение: мы можем построить s / 2 (округление в нижнюю сторону) тоннелей или сделать граф связным, построив n – 1 тоннель (при s / 2 >= n – 1). Действительно, рассмотрим те вершины, для которых ki > 1. Соединим эти вершины в цепочку тоннелями, а вершины для которых ki = 1 будем присоединять к этой цепочке, пока возможно. Пусть мы провели менее s / 2 тоннелей и не можем провести еще один. Значит, у нас осталась ровно одна вершина j, степень которой не более, чем kj – 2. Тогда получаем, что для этой вершины kj > 1, то есть эта вершина принадлежит построенной цепочке, а все вершины, для которых ki = 1, уже присоединены к этой цепочке (иначе бы мы смогли провести еще один тоннель), то есть граф связен.

Если, проведя s / 2 тоннелей, мы получили связный граф, то ответ 0. В противном случае граф будет состоять из n s / 2 компонент связности, то есть нам потребуется провести еще хотя бы n s / 2 – 1 дорогу. На самом деле такого количества дорог нам будет достаточно. Проведем n s / 2 – 1 дорогу следующим образом. Выберем 2 различные компоненты связности (по дорогам или тоннелям) в текущем графе. Поскольку мы строили тоннели (и, возможно, дороги) только между различными компонентами связности, то каждая текущая компонента представляет собой дерево. Значит, в выбранных компонентах существуют вершины, степени которых не более 1. Выберем по одной такой вершине в каждой из выбранных компонент и соединим компоненты по этим вершинам (то есть вершины объединяем в одну, сохраняя ребра). Тем самым мы получили новую вершину (провинцию), из которой идет не более двух тоннелей, то есть мы не нарушили условия, поскольку k >= 2. Таким образом, мы сможем получить связный граф, построив дополнительно n s / 2 – 1 дорогу, что и является ответом к задаче.


Задача E.

Если x = 2, то ответ 0. Далее будем считать, что x > 2.

Для того, чтобы однозначно определить искомое число предметов t мы должны выбрать множество чисел ai, так чтобы для любого y от 2 до x представление y в режимах ai было уникальным, т.е. множества чисел b(y,i) = y / ai (округленное вверх) были попарно различны между числами y. Заметим, что для каждого i функция b(y,i) монотонна по y. Значит, если для некоторого i для чисел y и z (y < z) выполняется b(y,i) = b(z,i), то выполняется и b(y,i) = b(y + 1,i). Тогда для выбора необходимого множества чисел ai нам достаточно гарантировать для каждого y от 2 до x – 1 существование некоторого числа j, такого что b(y,j) < b(y + 1, j). Легко видеть, что b(y,j) < b(y + 1, j) тогда и только тогда, когда y делится без остатка на aj. Таким образом, необходимо, чтобы для каждого y от 2 до x – 1 существовало такое ai, что y делится на ai. Если некоторое число ai равно 1, то нам достаточно просмотреть список в этом режиме и ответ на задачу будет 1. В противном случае для выполнения условия нам необходимо и достаточно взять в множество просмотренных режимов все простые числа pi < x. Действительно, если мы не использовали число pi, то мы не сможем отличить числа pi и (pi + 1) (поскольку pi не будет делиться ни на одно из выбранных чисел). Наоборот, если мы взяли все простые числа меньшие x, то любое число от 2 до x - 1 будет делиться хотя бы на одно из них. Таким образом, нам необходимо проверить, встречаются ли все простые числа, меньшие x, среди ai. Поскольку количество простых чисел от 1 до x есть величина порядка O(x / ln(x)), то при больших x все простые числа, меньшие x, не смогут оказаться в наборе чисел ai. Например, верна оценка: при x > 20 * n, ответ будет -1. Значит, можно воспользоваться решетом Эратосфена для нахождения всех простых чисел, меньших x при x <= 20 * n и проверить, существует ли среди них число, не встречающееся среди ai. Если такое число существует, то ответ к задаче -1, иначе ответом будет количество простых чисел меньших x.


Задача F.

Если для некоторой скорости v1 мы смогли проехать из точки A в точку B, получив не более k попаданий, то для любой скорости v2 >= v1 мы так же сможем проехать из A в B. Значит, можно воспользоваться бинарным поиском для нахождения ответа.

Пусть мы зафиксировали скорость танка v. Необходимо посчитать, сколько танков сумеют выстрелить по нам в процессе езды. Рассмотрим вражеский танк i, находящийся в точке P плоскости. Он может пытаться прицелиться в наш танк двумя способами: повернуть башню на точку B или повернуть башню на точку A и затем поворачиваться от точки A к точке B. В первом случае достаточно сравнить время передвижения танка от A к B со временем поворота врага на точку B. Если вражеский танк сумеет прицелиться в точку B раньше, чем мы сумеем туда приехать, то он сможет сделать выстрел. Далее рассмотрим вторую возможную стратегию врага. Проведем перпендикуляр PQ к прямой AB. Разобьем отрезок AB на 2 части: AQ и QB (если Q не лежит на отрезке AB, то одна из частей будет пустой, а другая представляет собой отрезок AB – тогда за Q обозначим конец отрезка AB, ближайший к основанию перпендикуляра). Рассмотрим первую часть отрезка - AQ (до основания перпендикуляра). Легко проверить, что при постоянной угловой скорости поворота башни, линейная скорость прицела врага вдоль отрезка AB будет монотонно убывать. С учетом того, что скорость нашего танка вдоль AB постоянна, получаем, что функция разности координат прицела и танка на отрезке AQ от времени выпукла вниз (вторая производная отрицательна). Так же в этом можно убедиться, найдя вторую производную этой функции. Тогда мы можем воспользоваться троичным поиском для нахождения минимума этой функции на временном интервале, соответствующем преодолению танком отрезка AQ. Если в точке минимума функция отрицательна, то значит, враг смог прицелиться на наш танк и выстрелить. В противном случае, танк будет следовать впереди прицела на всём отрезке AQ. (Пользуясь аналогичными утверждениями, можно искать, например, минимум функции разности времен достижения некоторой точки D отрезка AQ прицелом врага и нашим танком). Можно избавиться от троичного поиска, найдя момент, когда скорости прицела и нашего танка сравняются, и проверить, кто будет ближе к точке B в этот момент. Но при этом необходимо аккуратно обработать случаи, когда одна скорость всегда больше другой на всём отрезке.

Далее рассмотрим вторую часть отрезка - QB (после основания перпендикуляра). Если враг не смог выстрелить в наш танк на первой части отрезка, то, стало быть, к моменту прицеливания врага на точку Q, наш танк будет находиться ближе к точке B, чем прицел. Аналогично первой части отрезка AB можно убедиться, что линейная скорость прицела вдоль QB будет монотонно возрастать. Пусть в какой-то момент времени прицел врага догнал танк в точке C отрезка QB. Тогда в этот момент скорость прицела должна быть выше скорости танка (иначе, танк догнать бы не удалось). В силу монотонности скорости прицела получаем, что и на оставшемся отрезке CB скорость прицела врага будет выше скорости танка, значит, прицел достигнет точки B раньше. Соответственно, если вражеский прицел достиг точки B позднее нашего танка, то танк находился впереди прицела и на всем отрезке QB. Таким образом, для определения возможности стрельбы врага нам достаточно проверить времена достижения точки B.

Проделав такие вычисления для каждого из n врагов, мы получим число попаданий по нашему танку и, сравнив это значение с числом k, перейдем в нужную ветку бинарного поиска скорости.

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 66
  • Проголосовать: нравится
  • +24
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски
Задача А.

Для удобства обозначим размеры монстра через x1, x2, x3.

1. Решение за O(min(k, x1 + x2 + x3))

Всего можно провести не более (x1 – 1) + (x2 – 1) + (x3 – 1) разрезов, поэтому можно считать, что k <= x1 + x2 + x3 – 3. Для каждой из трёх координат будем хранить число ai – количество уже проведенных разрезов вдоль соответствующей координаты. Проделаем k раз следующую операцию: рассмотрим те числа ai, которые мы можем увеличивать (то есть вдоль соответствующей координаты еще не проведены все возможные разрезы, назовем такие координаты «неполными»). Среди полученных ai выберем наименьшее число aj и проведем разрез вдоль соответствующей координаты (в результате число aj увеличится на 1). Теперь рассмотрим получившееся после k операций множество {a1, a2, a3}. Заметим, что при таком алгоритме наибольшее число этого множества будет принимать наименьшее возможное значение, а наименьшее число – наибольшее возможное значение. Это, в свою очередь, гарантирует максимальность произведения (a1 + 1) * (a2 + 1) * (a3 + 1) при фиксированной сумме a1 + a2 + a3 = k.

2. Решение за O(1)

Вместо того чтобы моделировать все k операций, можно быстро определить, чему будут равны числа ai после применения алгоритма, описанного в пункте 1.

Пусть x – наименьшее среди чисел xi - 1. Если x * 3 >= k, то на каждой итерации алгоритма множество «неполных» координат будет содержать все 3 координаты. Значит, за первые (k / 3) * 3 шага, каждое из чисел ai мы увеличим на (k / 3). Далее, в зависимости от остатка k при делении на 3, от 0 до 2 чисел ai будут увеличены на 1. Таким образом, числа ai найдены.

В противном случае (x * 3 < k) за первые x * 3 шага каждое из чисел ai мы увеличим на x. После этого у нас останется не более двух «неполных» координат, обработать которые можно аналогичным образом, выбрав наименьшее значение x среди них.


Задача B.

Можно считать, что у нас всегда ровно n призовых мест, но за некоторые из них дается 0 очков.

Отсортируем все места по количеству призовых очков (bi), а участников - по количеству уже набранных очков (ai). Определим, в каком случае Вася сможет занять наилучшее место. Понятно, что в лучшем случае сам Вася получит b0 очков (где b0 – наибольшее среди чисел bi). Будем считать, что теперь у него стало в сумме v очков. Теперь нам надо раздать остальные призовые очки участникам так, чтобы количество участников, обогнавших Васю, было наименьшим. Для этого определим, какое наибольшее число призов мы сможем вручить так, чтобы получившие их участники не обогнали Васю. Заметим, что если мы смогли вручить таким образом k призов, то мы так же сможем вручить и k наименьших (с точки зрения количества призовых очков) призов. Далее очевидно верно следующее утверждение: если приз в t очков мы можем вручить как участнику i, так и участнику j, причем ai > aj, то выгоднее вручить этот приз участнику i, более формально: если существует способ раздать k призов, при котором данный приз достался участнику j, то существует и способ раздать k призов, при котором данный приз достался участнику i. Строго доказать это можно следующим образом. Рассмотрим способ вручить k призов, при котором участник j получил приз в t очков, а участник i – s очков или не получил приза вовсе. В первом случае можно поменять призы участников i и j. Действительно, поскольку ai > aj, и ai + s < v (поскольку участник i получил приз), то aj + s < v, а ai + t < v по предположению. Во втором случае можно приз t просто отдать участнику i, а участника j оставить без приза. В обоих случаях мы получили допустимый вариант вручения k призов, при котором участник i получил приз t.

Теперь, пользуясь полученными утверждениями, можно раздавать призы жадно следующим образом. Будем раздавать призы, начиная с наименьшего приза. При этом будем просматривать участников, начиная с наилучшего (разумеется, Васю и наилучший приз мы не рассматриваем). Для каждого приза i будем двигаться по списку участников (j), пока не получим bi + aj < v. Если такого участника не нашлось, то мы больше не сможем выдать приз так, чтобы получивший его участник не обогнал Васю. В этом случае алгоритм останавливается и ответом будет n – k, где k – количество уже врученных призов. Если такой участник j нашелся, то мы можем ему вручить приз bi и перейти к следующему призу. Итого, сложность этого шага есть O(n).

Аналогично определяется наихудшее место, которое может занять Вася. Для этого ему нужно вручить наихудший приз, после чего вручать призы остальным участникам, двигаясь по списку призов в порядке убывания количества очков и по списку участников в порядке возрастания.

Общая сложность алгоритма есть O(n * log(n)) за счет необходимости сортировки.

 

Задача C.

Заметим, что если мы поставили в позицию p строки s некоторый символ c, то он не влияет на благозвучие, получаемое за счет символов в позициях (p+2) и больше. Таким образом, мы получаем стандартную задачу динамического программирования. Состояние описывается тремя параметрами: p – количество уже просмотренных букв строки (или номер символа строки, который мы на данный момент рассматриваем), c – предыдущий символ строки, t – количество разрешенных изменений символов. Пересчет состояния осуществляется перебором буквы, которую мы будем ставить на место p, при этом надо учитывать, что мы можем изменять букву только в случае, когда t > 0. Итого, получаем формулу пересчета:

d[n][*][*] = 0

d[p][c][t] = d[p + 1][s[p]][t] + bonus[c][s[p]] при t = 0

d[p][c][t] = max(d[p + 1][c’][t – (c’ <> s[p])] + bonus[c][c’])

где n - длина строки s.

Сложность алгоритма - O(n * k * h^2), где h - размер алфавита (в данной задаче h = 26).

Полный текст и комментарии »

Разбор задач Codeforces Beta Round 66
  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

Автор ashmelev, 13 лет назад, По-русски
Добрый день!

Авторами сегодняшнего контеста являются Евгений Лазарев (Нижегородский ГТУ) и я (Алексей Шмелев, Нижегородский ГУ)

Сегодня вам предстоит помочь мальчику Васе cориентироваться в виртуальном мире компьютерных игр.

Обращаем внимание, что раунд пройдет в нестандартном формате - 6 задач стоимостью 500, 1000, 1000, 1500, 1500 и 2000 баллов.

В связи с измененным количеством задач продолжительность раунда увеличена до 2 часов 30 минут.


Выражаем благодарность Марии Беловой за перевод условий, Артему Рахову и Александру Куприну за помощь в подготовке задач, написание альтернативных решений и создание хитрых тестов.

Желаем удачи и успешной сдачи решений!

UPD: Приносим извинения за неточности в задаче E и последующие неверные ответы на вопросы некоторых участников.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +61
  • Проголосовать: не нравится