Codeforces Round #444 (Div. 2) Editorial

Revision ru7, by Denisson, 2017-11-04 19:17:42

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

887A - Div. 64

Автор: .tx.

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

Решение: 32056640.

887B - Cubes for Masha

Автор: .tx.

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

Решение: 32056754.

887C - Solution for Cube

Автор: .tx.

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

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

Решение: 32056890. Denisson

Решение: 32056905. .tx

887D - Ratings and Reality Shows

Автор: .tx.

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

Решение: 32057284.Denisson

Решение: 32057313..tx

887E - Little Brother

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

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

Решение: 32057661.Denisson

Решение: 32057674..tx

Решение: 32057685. cdkrot

887F - Row of Models

Автор: 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).

Решение: 32057999. Denisson

Решение: 32058014. Denisson

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Denisson 2017-11-05 10:30:48 32
en3 English Denisson 2017-11-04 22:40:31 3 Tiny change: ' an array ai we can ch' -> ' an array $a_i$ we can ch'
en2 English Denisson 2017-11-04 22:37:36 15 Tiny change: '1-04]\n\n[Решение.](https:/' -> '1-04]\n\n[Solution.](https:/'
en1 English Denisson 2017-11-04 22:21:02 4836 Initial revision for English translation
ru8 Russian Denisson 2017-11-04 20:14:15 507
ru7 Russian Denisson 2017-11-04 19:17:42 5
ru6 Russian Denisson 2017-11-04 19:12:46 178 Мелкая правка: '#Еще раз п' -> '###Еще раз п' (опубликовано)
ru5 Russian Denisson 2017-11-04 19:11:22 122
ru4 Russian Denisson 2017-11-04 19:09:42 1736 Мелкая правка: 'ь ровно одно меньше, тогда пр' -> 'ь ровно один такой элемент, тогда пр'
ru3 Russian Denisson 2017-11-04 18:50:43 915
ru2 Russian Denisson 2017-11-04 18:32:37 1541 Мелкая правка: 'enisson]\nРешение:' -> 'enisson]\n\nРешение:'
ru1 Russian Denisson 2017-11-04 18:01:18 365 Первая редакция (сохранено в черновиках)