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

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

 

A. Контрольная работа

Переберем префикс заданий, которые решит Коля. Найдем время, которое он потратит, если будет сам решать все задания и найдем максимальное время, которое он потратит на одно задание в таком случае. Понятно, что если он будет списывать, то списывать надо именно самое долгое задание из тех, что он делает. Тогда время, которое Коля потратит равно S - max(0, M - t0). Теперь найдем наибольший префикс, у которого это время не превышает t.

B. Многоножка

Чтобы решить эту можно отсортировать все записи по количеству левых ног. Дальше будем перебирать количество левых ног по возрастанию. Если левых ног li, то потенциально могут быть верными, первые i записей, а все последующие записи точно не верны (За исключением количества ног равных li).

Теперь нужно узнать, сколько записей из первых i будут верны. Запись c номером j ≤ i верна, если rj ≤ n - li. Нахождение всех таких rj является стандартной задачей и решается, например, деревом отрезков.

Также нужно было обратить внимание, что сумма чисел в ответе должна быть равна n и корректно обрабатывать случай, где все записи могут быть неверны.

C. Двоичное дерево

Чтобы минимизировать количество дней, которые придется потратить Васе, нужно минимизировать высоту итогового бинарного дерева — если глубина листа в итоговом дереве равна h, то Вася потратит 2h - 1 - n дней на то, чтобы подвесить необходимое число вершин.

Заметим, что если в дереве есть вершина степени больше 3, то задание выполнить не получится — в полном бинарном дереве все вершины имеют не больше трех соседей. Обратим внимание, что корень в ответе имеет ровно двух сыновей.

Таким образом, чтобы решить задачу, нужно перебрать корень — вершину степени не больше 2, и выбрать корнем такую вершину, что максимальное из расстояний от нее до всех остальных минимально. Это и будет высота итогового дерева.

D. Пробирки и реактивы

Приведем конструктивный алгоритм в несколько этапов:

  • Если sum(mini) > sum(vi) — ответ «NO»;
  • Если sum(maxi) < sum(vi) — ответ «NO»;
  • Нальем в каждую пробирку mini·pi / 100 миллилитров реактива ci;
  • После этого для каждого реактива i отсортируем пробирки, для которых cj = i по возрастанию pj и будем по очереди наливать в них оставшийся реактив номер i;
  • В каждую пробирку нальем еще (maxj - minjpj / 100 миллилитров i-го реактива или меньше, если он закончится;
  • Все оставшееся от реактивов разольем по пробиркам любым способом: в i-ю пробирку суммарно можно налить любое количество жидкости, не превосходящее summaryi·100 / pi (summaryi — суммарное количество жидкости в ней на текущий момент);
  • Если разлить не получилось и жидкость осталась — ответ «NO»;
  • Единственная оставшаяся проблема — в каких-то пробирках все еще может быть меньше mini миллилитров жидкости;
  • Для исправления этого в пробирке i, сначала перельем из всех остальных пробирок j реактивы, отличные от cj, в i-ю пробирку, так, чтобы в j-й пробирке осталось хотя бы minj жидкости;
  • Если и этого не хватило, перельем из остальных пробирок j жидкость номер cj (теперь это не испортит условие на процентное содержание).

После этих действий получившееся разделение реактивов на пробирки всегда будет удовлетворять всем условиям задачи.

Напоследок отметим, что в этой задаче могли быть определенные проблемы с точностью. Тесты жюри были построены в этом смысле довольно гуманно, но после тура Петр Митричев (которого мы поздравляем с победой в отборочном раунде) показал тест, в котором происходят существенные потери точности. Мы постараемся в дальнейшем избегать тонкостей с точностью в задачах с вещественными числами.

E. Размен денег

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

Пусть на очередном шаге мы рассмотрели все монеты, стоимость которых не превышает X и мы можем заплатить любую сумму до Y включительно. Пусть суммарная стоимость монет, каждая из которых стоит больше X, но не больше Y + 1 равна sum. Тогда, если sum = 0, то Y + 1 мы не сможем представить с помощью этого набора. Иначе, перейдем к состоянию, что рассмотрены все монеты, стоимость которых не больше Y + 1, и мы можем представить любую сумму до Y + sum включительно.

Заметим, что стоимость максимальной монеты, которую мы рассмотрели растет как минимум также быстро как числа Фибоначчи. Значит, этот процесс завершится за O(log Answer) итераций.

Чтобы решить исходную задачу, необходимо научиться находить сумму чисел меньших X на отрезке. Если делать это за O(log n), то можно решать задачу суммарно за O(m log n log Answer).

Эта задача является стандартной. Рассмотрим метод, который требует линейное количество памяти. Для этого отсортируем все числа в исходном массиве и будем отвечать на все запросы параллельно. На очередной итерации для каждого запроса известно текущее максимальное количество денег, которое можно получить. Отсортируем все запросы по нему. Далее будем добавлять в дерево Фенвика числа исходного массива в порядке возрастания и в нужный момент обновлять границу для очередного запроса.

F. Отборочный раунд, задача F

Ответ «NO» бывает только в одном случае, когда d не делится на наибольший делитель всех чисел ai. В любом другом случае ответ всегда существует. Для начала мы научимся получать хоть какой-то ответ без ограничения на значения, предварительно поделив все ai и d на gcd(a1, ..., an). Если n = 1, то x1 = d / a1. В других случаях, мы будем подбирать для каждого префикса [1, p] такие xi, p, что a1x1, p + ... + apxp, p = gcd(a1, ..., ap). Делается это индуктивным методом. x1, 1 = 1. Пусть мы уже нашли xi, p и хотим найти xi, p + 1. С помощью расширенного алгоритма Евклида мы находим s и t: s·gcd(a1, ..., ap) + t·ap + 1 = gcd(gcd(a1, ..., ap), ap + 1) = gcd(a1, ..., ap + 1). Тогда для i ≤ p xi, p + 1 = s·xi, p и xp + 1, p + 1 = t. Получив xi, n, вычисляем xi = d / gcd(a1, ..., anxi, n = d·xi, n. Такое решение работает за O(n2), что не подходит под ограничения. Чтобы сократить время работы, мы выберем среди ai подмножество, у которого наибольший общий делитель такой же как у всего множества и такое что нельзя уменьшить. Для этого мы будем перебирать от a1 до an и брать число в подмножество, если оно уменьшает количество различных простых делителей. Таким образом, выбранное подмножество содержит не более 7 элементов, так как максимальное количество простых у числа меньше либо равного 106 равно 7. Для чисел из подмножества мы запускаем вышеописанный алгоритм, а для чисел не вошедших в множество, мы просто выставляем xi = 0.

Теперь алгоритм работает за O(n), но не выполняются условия, что xi по модулю не превышают 106 и среди них не должно быть нулей. Для этого опишем процедуру нормализации. Сначала выполним для xi первое условие. В первую очередь, сделаем все xi для i > 1 неотрицательными и меньшими a1. Это делается простой операцией эквивалентного изменения: мы вычитаем из x1 kai и прибавляем к xi ka1, где k = (xi mod a1 - xi) / a1. Отметим, что результаты выполнения операции влезают в 64-битный тип данных, так как x1 по модулю не может превзойти |d - a2x2 - ... - anxn| < 106·106·105. Теперь пройдёмся по всем xi, начиная со второго до последнего, и с каждым будем последовательно производить операцию: вычесть a1 из xi и прибавить ai к x1. Заметим, что существует i, что после применения операции к x1, ..., xi получилось 0 ≥ x1 ≥  - 106. Пусть не существует такого i, тогда все xi стали отрицательными, чего случиться не могло, так как a1x1 + ... anxn даёт d, то есть положительное число. Научившись получать |xi| ≤ 106, осталось сделать их ненулевыми. Разобьём все нули на пары, возможно, кроме одного. В каждой паре i и j присвоим xi = aj и xj =  - ai. У нас, возможно, остался единственный индекс p, для которого xp = 0. Мы рассмотрим несколько случаев:

  • Если существует xj, которое по модулю не равно ap, тогда мы применяем операцию: вычитаем sign(xj)ap из xj и прибавляем sign(xj)aj к xp.
  • Если же такого xj не существует, но ap ≤ 5·105, тогда к любому xj можно применить операцию: прибавить sign(xj)ap к xj и вычесть sign(xj)ap из xp.
  • В противном случае должен найтись aq, такой что aq ≠ ap. Если такого не существует, то все ai = a1, а, значит, из-за нормировки на наибольший общий делитель ai = a1 = 1 и должен был выполниться второй случай. Мы проводим операцию: вычтем sign(xj)ap из xq и прибавим sign(xj)aqк xp. После этого xq равно нулю. Но теперь если n > 2 для q выполнится первый случай, а если n = 2, то для q выполнится второй случай, так как d = aqap ≤ 106.

    Нужно отметить, что операцию нормировки нужно производить для каждого префикса в алгоритме, описанном в первом параграфе, чтобы числа помещались в 64-битный тип данных. За дальнейшими подробностями можно обратиться к коду решения жюри, выложенному вместе с тестами.


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