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

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

Еще раз приносим извинения участникам за допущенные нами ошибки при подготовке раунда.

887A - Div. 64

Автор: .tx.

Если в строке нет единиц, то ответ "NO", так как оставшееся число должно быть положительным. Иначе найдем самую левую единицу и проверим, что после нее есть хотя бы 6 нулей.

Решение.

887B - Кубики для Маши

Автор: .tx.

Ответ никогда не превосходит величины 98. Переберем числа от 1 до 99 и найдем первое такое, что его нельзя собрать из кубиков.

Решение.

887C - Сборка кубика

Автор: .tx.

Возможных вариантов входных данных, на которые ответ "YES", не более 12, не учитывая перестановки цветов. Их все можно было записать в массив.

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

Решение. Denisson

Решение. .tx

887D - Рейтинги и ток-шоу

Автор: .tx.

Посчитаем два массива префиксных сумм на событиях данных во входных данных. Один по значениями (a, b), другой со значениями (c, d). Ответом является момент времени 0 или момент сразу после какого-то из событий данных в задаче. Воспользуемся методом двух указателей. Один указатель будет показывать после какого события V мы хотим устроить ток-шоу, а другой на момент времени сразу после его окончания. Тогда мы можем устроить ток-шоу, если минимум из префиксных сумм на значениях (c, d) от элементов между указателями не меньше, чем разность префиксных сумм на значениях (a, b) и (c, d) от элемента V. Также нужно не забыть проверить, что рейтинг Изабеллы не стал отрицательным раньше проведения ток-шоу.

Решение. Denisson

Решение. .tx

887E - Маленький брат

Авторы: .tx, Denisson.

Центр искомой окружности лежит на серединном перпендикуляре к отрезку AB, где A, B — точки данные в условии. Если окружность с центром в середине отрезка и радиусом половины длины отрезка подходит, то она будет являться ответом. Иначе переберем по какую сторону будет лежать центр искомой окружности относительно прямой AB. Каждая изначально нарисованная окружность блокирует непрерывный интервал допустимых значений для искомой окружности. Границы этого интервала можно найти бинарным поиском. Теперь необходимо найти минимальное незаблокированное значение для радиуса. Это можно сделать, например, с помощью метода сканирующей прямой.

Решение. Denisson

Решение. .tx

Решение. cdkrot

887F - Модельный ряд

Автор: Denisson.

Для каждого элемента массива ai рассмотрим x элементов справа от него. Если нет ни одного элемента меньше пометим ai как "-1" и назовем "плохим". Если есть ровно один такой элемент, тогда проведем ребро из ai в этот элемент. Иначе свап элементов массива никогда не сделает ai плохим. Если теперь нет ни одного плохого элемента в массива, тогда ответ "YES". Иначе найдем самый левый плохой элемент bad в массиве. X элементов после него не меньше, чем он сам. Все элементы перед ним также не меньше, чем он сам, так как иначе элемент меньше, чем bad, также был бы плохим. Свапать bad с элементом на суффиксе также не имеет смысла, так как на его место встанет элемент еще меньше и позиция останется плохой. Таким образом, свапать bad с другими элемента массива не имеет смысла. Единственный способ удовлетворить всем условиям — свапнуть один из x элементов после bad с другим элементом на оставшемся суффиксе без учета отрезка длины x после bad. Попробуем сделать это явно. Тогда должны выполняться следующие условия. Пусть мы зафиксировали элемент y на оставшемся суффиксе, тогда такое свап может быть ответом, если y < bad. Также на суффиксе после y и на отрезке между y и отрезком длины x после bad не должно быть плохих элементов. Элемент, с которым мы свапаем y, из отрезка длины x после bad должен быть меньше любой ссылки на y. Нужно не забыть проверить, что после свапа для элемента y справа от него найдется элемент меньше него на расстоянии не больше, чем x.

Время: O(n) или O(nlogn).

Решение. Denisson

Решение. Denisson

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

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

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

Привет, Codeforces!

Раунд состоится в пятницу, 3 ноября в 19:05 (по московскому времени).

Задачи готовили Антон Гардер (.tx) и я, Шпаковский Денис (Denisson). Спасибо 300iq, Glebodin, FalseMirror, cdkrot, Arpa, Starcall за помощь в подготовке раунда, vintage_Vlad_Makeev за координирование и перевод условий, MikeMirzayanov за платформы Codeforces и Polygon.

Вам будет предложено 6 задач и 2.5 часа на их решение.

Надеемся, раунд вам понравится. Удачи!

Разбалловка: 500—1000—1500—2000—2500—3000

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

Появился разбор.

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

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