Еще раз приносим извинения участникам за допущенные нами ошибки при подготовке раунда.
887A - Div. 64
Автор: .tx.
Если в строке нет единиц, то ответ "NO", так как оставшееся число должно быть положительным. Иначе найдем самую левую единицу и проверим, что после нее есть хотя бы 6 нулей.
887B - Кубики для Маши
Автор: .tx.
Ответ никогда не превосходит величины 98. Переберем числа от 1 до 99 и найдем первое такое, что его нельзя собрать из кубиков.
887C - Сборка кубика
Автор: .tx.
Возможных вариантов входных данных, на которые ответ "YES", не более 12, не учитывая перестановки цветов. Их все можно было записать в массив.
Альтернативным решением является написание функции поворота заданной грани кубика и последующей проверкой на то, что кубик собран.
887D - Рейтинги и ток-шоу
Автор: .tx.
Посчитаем два массива префиксных сумм на событиях данных во входных данных. Один по значениями (a, b), другой со значениями (c, d). Ответом является момент времени 0 или момент сразу после какого-то из событий данных в задаче. Воспользуемся методом двух указателей. Один указатель будет показывать после какого события V мы хотим устроить ток-шоу, а другой на момент времени сразу после его окончания. Тогда мы можем устроить ток-шоу, если минимум из префиксных сумм на значениях (c, d) от элементов между указателями не меньше, чем разность префиксных сумм на значениях (a, b) и (c, d) от элемента V. Также нужно не забыть проверить, что рейтинг Изабеллы не стал отрицательным раньше проведения ток-шоу.
887E - Маленький брат
Центр искомой окружности лежит на серединном перпендикуляре к отрезку AB, где A, B — точки данные в условии. Если окружность с центром в середине отрезка и радиусом половины длины отрезка подходит, то она будет являться ответом. Иначе переберем по какую сторону будет лежать центр искомой окружности относительно прямой AB. Каждая изначально нарисованная окружность блокирует непрерывный интервал допустимых значений для искомой окружности. Границы этого интервала можно найти бинарным поиском. Теперь необходимо найти минимальное незаблокированное значение для радиуса. Это можно сделать, например, с помощью метода сканирующей прямой.
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).
