7 августа стартовал второй этап SnarkNews Summer Series 2016. Как и несколько предыдущих серий, SNSS-2016 проходит на системе Яндекс.Контест. Опубликовано расписание серии.
По просьбам участников отдельно публикую ссылку для регистрации и входа во второй раунд. В комментариях к этому сообщению по окончании раунда в соответствии с расписанием можно будет обсудить задачи второго раунда.
Также напоминаю, что первый раунд завершится 11 августа в 14:00 (стартовать виртуальный контест возможно до этого момента).
Можете пожалуйста рассказать, как решать D, E, F?
F: для начала упростим функцию. Заметим, что можно убрать isnotless и сделать вместо этого перебор по а, b для выражения min(n, lcm(a, b) + gcd(a, b)) - max(a, b) + 1. Следующее наблюдение — lcm(a, b) + gcd(a, b) обычно больше n, так что мы можем предположить, что оно всегда будет не меньше n, а потом как-то подсчитать те случаи, когда это выражение меньше, и вычесть их вклад.
Мы можем перебрать lcm(a, b) и gcd(a, b) (второй является делителем первого), число способов получить такую пару равно 2 в степени числа простых в lcm(a, b) / gcd(a, b) — для каждого простого мы можем выбрать, в какое из двух чисел его включить. Дальше поскладывать все аккуратно, посчитать частичные суммы и т.д., и мы сможем отвечать на запрос за О(1).
Код.
Задача E. Утверждается, что при данном значении k оптимальнее всего все числа h[1], ..., h[k] свести к их среднему арифметическому. Вернее, если s = (h[1] + ... + h[k]) / k, то оптимальное число есть s или s + 1. Далее, растяжение одной пружины на d на самом деле стоит d * (d + 1) / 2 единиц энергии. Для нахождения ответа теперь достаточно подсчитать частичные суммы по h и h^2. Также на C++ понадобится реализация длинной арифметики.
P.S. Может ли кто-нибудь объяснить, почему сводить числа надо именно к среднему арифметическому?
В общих чертах, опуская детали, имеют место быть такие рассуждения:
Выпишем целевую функцию, которую надо минимизировать
Чтобы найти оптимальный s решим уравнение: f'(s) = 0:
Отсюда получим, что
.
Заходит, можно и с бинпоиском. У меня в решении самое долгое — длинная арифметика.
А разве __int128 там не хватает?
У меня чуть-чуть другое решение, которое зашло в дорешивание, которое не предполагает использования длинной арифметики, но при этом достаточное медленное, чтобы со скрипом входить в ТЛ.
Я добавлял по одной точки в множество, понятно, что это двигает точку оптимума вправо. Также понятно, что целевая функция при фиксированном множестве пружин является кусочно-квадратичной. Таким образом, можно оценить, где точка минимума у текущего параболического куска, и если до неё случается излом (мы проходим через какую-то точку), то аккуратно проходим через него, обновляя коэффициенты квадратного трёхчлена, а иначе считаем ответ по формуле. Не очень приятно в написании, до конца тура не отдебагалось :\
Глупый вопрос, а как было нормально писать A? Во время контеста я пытался что-то умное написать, после контеста заслал пересечение отрезков в предположении, что все точки далеко друг от друга и точек пересечения всех прямых и оно зашло. Вроде бы понятно, как такие решения завалить.
Просто надо было проникнуться духом SNSS, тогда бы не осталось сомнений, что 3 фора и пересечение отрезков это AC.
Ну вот в третьем раунде дух snss подвел, у меня там в C 10^8 операций сложения long long не зашло.