Russian Code Cup 2012: подробный разбор задач с отборочного раунда (полуфинал)

В прошлую субботу, 16 июня, завершился отборочный раунд Russian Code Cup 2012. Задачи отборочного раунда посложнее, чем были на квалификации – ну на то он и полуфинал. Я уже рассказывал о том, что предлагалось участникам на предыдущих онлайн-турах, разбирал подробно варианты решений (Q1, Q2, Q3).

В отборочный раунд было приглашено 600 человек. 434 человек смогли решить хотя бы одну задачу. Все задачи решили только двое. 50 лучших перешли в финал. Всего за 4 часа тура было отправлено в проверяющую систему 3190 решений.

Итак, перейдем к самим задачам. Я пострался объяснить их так, чтобы решения были понятны даже делающим первые шаги в спортивном программировании (да и в программировании вообще).

Епрестановка

Суть задачи заключалась в том, чтобы определить, можно ли, путем применения в произвольном порядке двух типов перестановок, переместить элемент с указанной позиции на указанную в списке значений. По условию задачи можно было применять так называемую епрестановку, меняющую первые два элемента местами, и сложную перестановку, задаваемую правилом-набором значений (a1, a2, ..., aN), где каждое из значений определяет порядковый номер позиции, на которую можно переместить число с этой позиции. К примеру, последняя двойка в правиле перестановок (1,4,3,2) означает, что с последней позиции можно переставить на вторую, а с нее — на последнюю. Собственно, в итоге и требуется дать ответ вида «Yes/No» на входные данные, содержащие этот список (из N значений) и запрос в виде (позиция1, позиция2) — «можно ли переместить элемент с позиции 1 на позицию 2».

Эта задача была простейшей на контесте, с ней справились 411 человек, первое прошедшее тесты решение было предложено Жуковым Дмитрием на 3 минуте 31 секунде с начала раунда.

Очевидно, что все перестановки в конечном счете сводятся к набору циклов. В приведенном выше примере цикла три — 4->2->4->2… 1->1->1… 3->3->3… То есть, если бы у нас была только операция «применить перестановку p», то для двух элементов ai и bi ответ был бы «Yes» тогда и только тогда, когда эти элементы лежали бы на одном цикле в перестановке p.

Подумаем о том, что происходит при применении «епрестановки» z. Если изначально первый и второй элементы лежали в разных циклах, то применение «епрестановки» дает нам возможность переставить какой-то элемент из одного из этих двух циклов в другой.

Теперь можно сформулировать и общее решение.

• Разобьем всю перестановку p на циклы.
• Для каждого запроса ai и bi ответ «Yes» если ai и bi лежат в одном цикле, или если в цикле одного из них присутствует первый элемент, а в цикле другого — второй.

Разбиение на циклы производится следующим образом:

// Введем вспомогательный массив col, инициалируем его −1. 
vector<int> col(n, −1);

// Далее попробуем поискать цикл, начиная с каждой позиции, которая не вошла в уже найденные
for (int i = 0; i < n; i++)
{
if (col[i] != −1) continue; // входила в уже найденные
int x = i;
do 
{
col[x] = i; // помечаем номером цикла
x = a[x];
} while (col[x] == −1);
}

Объединяем первые два цикла в один:

for (int i = 0; i < n; i++)
if (col[i] == 0) col[i] = 1; 

В итоге мы получили массив col, i-й элемент которого обозначает цикл, в который входит i-я позиция.

for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;

// остается проверить, входят ли два варианта в один цикл и вывести ответ.
cout << ((col[a — 1] == col[b — 1])? «Yes» : «No») << «n»;
}

Коронация

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

Подробную постановку задачи можно прочесть на странице раунда на официальном сайте Russian Code Cup.

Эта задача оказалась второй по сложности «с конца» – ее решило 313 человек. Первым правильное решение прислал Жуков Дмитрий на 12:50.

В задаче мы имеем взвешенное неориентированное дерево. То есть, граф, не имеющий петель и кратных ребер, ребрам которого («дорогам») прописаны «веса» — пропускная способность дорог.

В нем выделены две вершины — «столицы» — s и t. Нужно добавить ребро, не затрагивающее ни s, ни t, такое, чтобы поток из s в t был максимальным.

Пускай мы добавили ребро из вершины a в вершину b. Докажем, что между s и t будет не более двух простых путей (путь называется простым, если ребра в нем не повторяются). Докажем от противного. Предположим, нам удалось найти три пути.

Рассмотрим два случая:

• Хотя бы в двух из них встречается ребро ab. Здесь тоже два случая:
  • Ребро оба раза обходится в одном направлении. Возьмем одно из направлений a->b, тогда оба рассматриваемых пути содержат в себе подпуть <s; a; b; t>. Так как эти пути не равны, то не равны либо подпути <s; a>, либо <b;t>. В обоих случаях это означает то, что между вершинами дерева есть два различных пути, что противоречит его свойствам и условию задачи.
  • Ребро обходится в противоположных направлениях. Если так, то в дереве есть цикл <s; a; t; b; s>, что тоже противоречит условию задачи и свойствам нашего дерева.
• Ребро ab есть не более, чем в одном из них. Тогда оставшиеся два пути образуют цикл, а следовательно, простой цикл в дереве, что не может быть по условию задачи.

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

Рассмотрим второй путь, проходящий через ребро ab. Одним концом это ребро соединено к пути до вершины s, другим — к пути до вершины t. Теперь, если сдвинуть место соединения ab с <s;a> в узел, ближе к s, то пропускная способность не ухудшится. Аналогично рассуждая с дорогой до t, и, помня ограничение в задаче, приходим к тому, что новый путь, проходящий через узлы-столицы s,t и ребро ab в своем наиболее эффективном виде состоит из трех ребер — ребра из s, ребра ab и ребра из t.

В итоге получаем, что наш ответ состоит из двух путей, один из которых существовал до добавления ребра ab, а второй — ребро из s, ребро ab и ребро в t.

Получаем решение:

1. Найти путь из s в t по ребрам дерева,
2. Пропустить по нему максимальное число машин и, соответственно, уменьшить пропускную способность всех ребер на этом пути. При этом однозначно путь разрушится — ведь максимальное число машин соответствует наименьшей пропускной способности входящих в путь ребер.
3. Вероятно, останутся еще дороги (или одна дорога) из s и из t. Выберем те, у которых пропускная способность максимальна.
4. Соединив их ребром ab, посчитаем количество машин — минимальное значение из пропускных способностей двух ребер, выходящих из столиц.

Социофоб

Условие задачи стоит того, чтобы привести здесь его с минимальными сокращениями.

«Далеко не всем людям приятно постоянно находиться в толпе. Многие любят уединение и даже готовы за него платить. Именно поэтому ОАО «Радостные Железные Дороги» ввело на своем сайте продажи билетов новую услугу, называющуюся «Социофоб». Услуга необходима для того, чтобы дать возможность каждому пассажиру ехать в купе с наименьшим возможным количеством соседей. Суть ее заключается в следующем.

Пусть билеты продаются в некоторый вагон, в котором часть купе уже заполнена. Если в какой-то момент в этот вагон покупает билет очередной пассажир, ему продается место в самом незаполненном купе, то есть в купе, в котором количество людей не больше, чем во всех остальных. Если таких купе несколько, то выбирается купе с наименьшим номером. Если же пассажир из какого-то купе сдает свой билет, после чего разница между количеством людей в этом купе и в наиболее заполненном купе становится равной хотя бы двум, то из наиболее заполненного купе на освободившееся место пересаживается пассажир, который раньше других купил билет, то есть пассажир с наименьшим номером. Если наиболее заполненных купе несколько, то из них выбирается купе, ближайшее к тому, в котором был сдан билет. А если и таких несколько, то выбирается купе с наименьшим номером.

По данным о том, как пассажиры покупали и сдавали билеты, требуется вывести итоговое распределение пассажиров по купе. Гарантируется, что каждый раз, когда какой-либо пассажир покупает билет, в вагоне есть хотя бы одно свободное место».

Похоже, рассматриваемый поезд в задаче поистине огромный, так как количество операций продажи и возвратов билетов — до 200000, количество купе — до 50000.

Всего эту задачу решило 167 человек, из них первым был Кунявский Павел (23:19).

Одно из решений этой задачи выглядит следующим образом. Подготовим следующие структуры данных:

// массив, хранящий информацию о купе пассажира. Pas[i] = купе, -1 означает «ни в каком».
vector<int> pas(200000+1, -1);

// массив множеств – кто находится в купе. Cars[i] содержит набор идентификаторов пассажиров 
vector< set<int> > cars(50000 + 1);

Также будем поддерживать два множества (в C++, например, для этого можно воспользоваться set, в Java — TreeSet): zero и one. В zero будем хранить номера купе, в которых у нас наименьшее количество пассажиров, а в one — где больше всего.

set<int> zero;
set<int> one;

Изначально все купе пустые, поэтому помещаем их в список кандидатов на заполнение — zero.

for (int i = 1; i <= n; i++)
	zero.insert(i);

Других нам не нужно, так как разница между количеством пассажиров в различных купе никогда не будет превышать одного.

Операция продажи билета («+»). По условию задачи мы должны выбрать вагон с наименьшим номером, в котором меньше всего людей. Для этого возьмем наименьший элемент множества zero. Обновим соответственно информацию в pas и в cars. Затем удалим найденный элемент из zero и добавим его в one, так как теперь в этом вагоне столько же людей, как и во всех вагонах, лежащих в one. Если же zero станет пустым, то надо one и zero поменять местами, так как во всех купе стало одинаковое количество людей.

int car = *zero.upper_bound(0); // получаем номер купе
pas[++id] = car; // добавляем пассажира в список пассажиров 
cars[car].insert(id); // добавляем пассажира в набор пассажиров купе
zero.erase(car); // переносим купе из списка претендентов на заполнение
one.insert(car); // … в список заполненных купе

if (zero.empty()) // если вышло так, что претендентов на заполнение больше нет…
{
	zero = one; // переносим все заполненные купе в список претендентов
	zero.erase(-n);  zero.erase(2 * n);
	one.clear();  // очищаем список заполненных купе
 	one.insert(-n);  one.insert(2 * n);
}

Операция сдачи билета («-»). При помощи массива pas узнаем, в каком купе сидел пассажир. Удаляем пассажира из соответствующего купе.

int car = pas[x]; cars[car].erase(x); pas[x] = −1;

Узнаем, к какому множеству принадлежало купе car. Здесь есть следующие варианты:

• принадлежало множеству one — «заполненных купе». Тогда просто удаляем X из one и добавляем его в zero, то есть переносим купе в незаполненные;
• принадлежало множеству zero и множество one пусто. Тогда переносим все zero (претенденты на заполнение) в one (заполненные), оставляя в zero только купе, из которого выбыл пассажир.
• принадлежало множеству zero и множество one не пусто. Это единственный случай, в котором возникает ситуация, в которой разница между количеством пассажиров в купе могла стать равной двум. Для этого в множестве one находим первое купе, которое по номеру больше, чем наше купе, и последнее купе, которое по номеру меньше, чем наше купе. Затем из этих двух найденных купе выбираем ближайшее. Переносим его из множества one (заполненных) в множество zero («претенденты»). Также проводим корректировки в массиве купе cars и в массиве пассажиров pas.

set<int>::iterator ll = (one.upper_bound(car)); 
	ll--; // находим первое, по номеру меньше
	set<int>::iterator rr = (one.upper_bound(car)); // находим первое, по номеру больше
	if (abs(*ll - car) > abs(*rr - car)) // Из этих двух найденных купе выбираем ближайшее
	ll = rr; 
	int l = *ll;
	one.erase(l); 	zero.insert(l); // переносим из one в zero
	int p = *cars[l].upper_bound(0); 
	cars[l].erase(p); cars[car].insert(p); // переносим из купе в купе
pas[p] = car; 

Для вывода ответа на задачу воспользуемся массивом cars. Чтоб вывести информацию о пассажирах в i-м купе, достаточно вывести размер множества cars[i],

cout << cars[i].size() << ((cars[i].size() == 0) ? "n" : " ");

а затем и всех пассажиров, принадлежащих множеству cars[i].

set<int>::iterator en = cars[i].end();
en--;
for (set<int>::iterator it = cars[i].begin(); it != cars[i].end(); it++)
cout << *it << ((it == en) ? "n" : " ");

Монеты

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

Для иллюстрации приводится пример. Если в обращении есть монеты номиналом 1, 2 или 3 доллара, а Рисвинд заплатил 10 долларов вместо 9, то он мог это сделать, принявши монеты номиналом 2 за монеты номиналом 1, и заплатил, например, четыре монеты номиналом 2 и одну монету номиналом 2, которую он принял за номинал »1«.

Также он мог принять монеты номиналом 3 за монеты номиналом 2 и заплатить семь монет номиналом 1 и одну номиналом 3, которую принял за монету номиналом 2.

Сколько реально заплачено номиналом 1	Сколько реально заплачено номиналом 2	Сколько реально заплачено номиналом 3	Итого заплачено
—	реально 4 монеты (8 долларов, 4×2) 1 монета (2 доллара, 2×1) в представлении Рисвинда — 1 доллар (1×1)	—	реально 5 монет (10 долларов, 4×2+2×1) в представлении Рисвинда — 9 долларов (4×2+1×1)
реально 7 монет (7 долларов, 7×1)	—	реально 1 монету (3 доллара, 3×1) в представлении Рисвинда — 2 доллара (2×1)	реально 8 монет (10 долларов, 4×2+1×1) в представлении Рисвинда — 9 долларов (4×2+2×1)

Предположим, что Ринсвинд принял монету t за s. В последнем примере — монету 3 (t) за 2 (s). Это значит, что он набрал некоторую сумму V (в примере — 10 долларов), не используя монету s (в примере — 7 долларов), после чего положил еще k монет номер t, думая что это монеты номер s (в примере — 1 монету 3, думая, что это 2).

Другими словами, все разнообразие вариантов укладывается в две группы случаев:

• существуют целые числа V ≥ 0 и k > 0, такие что S = V + k · as и T = V + k · at, где T — реально заплаченная сумма, а S — сумма в представлении Рисвинда.
• сумму V можно набрать, не используя монету s.

Первое условие можно проверить за O(1). Заметим, что

k = (S − T) / (as — at);
V = S − k · as

Осталось проверить, что полученные числа целые, V ≥ 0, и k > 0.

Для того, чтобы проверить второе условие, воспользуемся методом динамического программирования. Пусть D[i][j] — можно ли при помощи первых i монет получить сумму j. База: D[0][0] = true. Переход: D[i][j] = D[i − 1][j] or D[i][j − ai]. Для реализации достаточно одного массива размера S. Время работы этого алгоритма O(S·n). Подробно про подход с использованием динамического программирования см. Разбор задач с прошлого тура, а также хороший материал с примерами и иллюстрациями.

Используя описанный метод, вычислим для каждой суммы V от 1 до S, мог ли Ринсвинд набрать эту сумму, не используя монету s. После этого переберем монету, которую Ринсвинд принял за s. Теперь проверка обоих условий осуществляется за O(1). Итоговая асимптотика решения — O(S · n2).

Задачу «Монеты» решил первым Петр Митричев на 17:06. Всего правильных решений мы получили 234, что ставит эту задачу на третье место с конца по сложности.

Разбор строки

В задаче рассказывается об алгоритме поиска словарных слов из данного текста — о так называемом жадном алгоритме, когда каждый раз из этого текста удаляется найденное слово. Приводится пример, что в некоторых случаях такой подход приводит к неправильным результатам. Скажем, для workingrass может быть удалено working и осталось бы некое rass, в то время как корректным решением было бы разбиение на три слова work / in / grass, каждое из которых имелось бы в словаре. Необходимо проверить, будет ли при указанном словаре жадный алгоритм отрабатывать верно, и, если не будет, привести пример строки, для которой разбиение на слова из словаря существует, но описанным алгоритмом оно не будет найдено. Если таких примеров несколько, необходимо найти кратчайший, то есть тот, длина которого не больше, чем у остальных. Если и таких несколько, нужно вывести любой.

Рассмотрим сначала ключевую идею, ведущую нас к решению задачи. Пусть есть строка t — искомый контрпример кратчайшей длины, и некоторое ее разбиение на слова из словаря w₁, w₂, ..., w_k. Пусть жадный парсер, который мы пытаемся сломать, при исследовании этой строки первым «откусит» от нее строку w.

Докажем следующее утверждение: если длина строки w не больше, чем сумма длин строк w₁, w₂, ..., w_k-1, то существует контрпример короче, чем строка t.

Пусть, для начала, длина строки t равна этой сумме. Тогда очевидно, что жадный парсер корректно отработает на строке t, так как от нее сначала будет «откушена» строка w, а потом строка w_k, так как именно она будет являться самым длинным префиксом строки, содержащимся в словаре.

В таком случае, пусть длина строки w меньше, чем сумма длин строк w₁, w₂, ..., w_k-1. Тогда существует число j такое, что w_j разбивается на префикс w_j1 и суффикс w_j2, причем w_j1 является суффиксом строки w (возможно, нулевой длины). Рассмотрим строку w_j2. Если для нее существует корректное разбиение на слова из словаря, то достаточно оставить в качестве контрпримера конкатенацию строк w_j2, w_j+1, w_j+2, ..., w_k, которая будет являться более коротким контрпримером. Если же для строки w_j2 разбиения на слова из словаря не существует в принципе, то более коротким контрпримером будет конкатенация строк w₁, w₂, ..., w_j.

Итак, теперь мы можем представить себе то, как выглядит искомый контрпример.

Разработаем эффективный алгоритм для его построения. Пусть для каждой строки из словаря мы знаем, у каких ее суффиксов и префиксов существует разбиение на слова из словаря (позднее будет объяснено, как вычислить эти данные). Переберем все строки из словаря на предмет того, не являются ли они той строкой w, которая будет «откушена» первой. Понятно, что предпоследняя строка из верного разбиения может заканчиваться только там же, где заканчивается некоторый префикс строки w, для которого разбиение есть. Переберем все такие префиксы. Теперь осталось только понять, какие строки могут являться последними в верном разбиении контрпримера. Во-первых, это должны быть строки, длина которых больше, чем длина еще непокрытого суффикса проверяемой строки w. Во-вторых, непокрытый суффикс строки w должен в точности совпадать с префиксом строки-кандидата на последнее место в разбиении соответствующей длины. И, наконец, суффикс строки-кандидата, непокрытый строкой w, не должен иметь корректного разбиения на слова из словаря.

Здесь уместно сделать одно важное замечание. Даже если непокрытый суффикс строки-кандидата имеет разбиение на слова из словаря, то, что мы проверяем в данный момент, все-таки может быть контрпримером. Однако, тогда контрпримером будет и сам по себе этот суффик, а тогда то, что мы проверяем, не является искомым кратчайшим контрпримером, и нас не интересует.

При таком подходе к решению задачи необходимо задаться еще одним вопросом. А что будет, если вместо строки w, которую мы проверяем, первой будет «откушена» другая строка, у которой w — префикс? В таком случае жадный парсер будет вести себя непредсказуемо, и может найти какое-нибудь разбиение. Однако для того, чтобы избежать этой участи, необходимо просто проверять строки на то, не являются ли они строкой w в порядке невозрастания их длин, и запоминать строки, которые мы уже проверили. Тогда каждая строка, с которой такая проблема вообще возможна, будет проверена к моменту возникновения проблемы, и мы сможем просто проигнорировать эту строку.

Теперь, когда общий алгоритм решения задачи есть, осталось решить задачу о проверке префиксов и суффиксов на разбиваемость, а также научиться быстро сравнивать нужные подстроки нужных строк на равенство. Вторая задача решается достаточно просто с помощью алгоритмов хеширования, которые сами по себе являются темой для отдельной статьи или лекции. Первая же задача решается с помощью динамического программирования. Пусть для всех префиксов строки t, длина которых строго меньше l, мы знаем, имеется ли их разбиение на строки из словаря. Чтобы проверить, существует ли разбиение префикса длины l, достаточно перебрать все строки из словаря и проверить существование такой, что выполняются два утверждения:

• суффикс изучаемого префикса соответствующей длины в точности равен строке из словаря
• префикс изучаемого префикса соответствующей длины разбивается на слова из словаря

Использовав для проверок на совпадение строк уже упомянутые алгоритмы хеширования и сделав аналогичные операции для всех суффиксов всех строк из словаря, мы за O(sumL × n), где sumL — суммарная длина всех строк, а n — их количество, вычислим все, что нам понадобится при реализации основной части. Заметим также, что реализация самого решения будет работать за то же самое время.

Задача «Разбор строки» оказалась (да и замышлялась) самым «крепким орешком», ее решило всего три человека, из них самым первым – Епифанов Владислав на 115:47.

Принц

В этой задаче необходимо найти минимальное время, за которое принц попадет к принцессе по одномерному коридору, не попав ни в одну ловушку. Известны расписание, размеры и места появления/исчезновения ловушек, а также скорость движения принца. Поскольку коридор одномерный, двигаться принц может либо по направлению к принцессе, либо от нее, либо никуда не двигаться вообще. Очевидно, существуют ситуации, когда выхода нет, и принц не попадет к принцессе — в этом случае нужно вывести Impossible.

Решение этой задачи стоит начать с того, что изобразить ловушки на плоскости, где одной координатой x является позиция в коридоре, а координатой x — время. Теперь задачу можно переформулировать в понятиях этой плоскости: требуется попасть из точки (0, 0) в точку (x, y) с минимальным y, при этом разрешено двигаться вертикально вверх (стоять на месте), по диагонали направо вверх и налево вверх (двигаться по коридору) и запрещено заходить в определенные прямоугольники (ловушки). Находиться на границе прямоугольника разрешено.

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

При движении по диагонали будем поддерживать множество прямоугольников, находящихся над текущей позицией. Так как на границе прямоугольников находиться можно, то прямоугольники, начинающиеся или заканчивающиеся на текущей «коридорной» координате, учитывать не будем. Прямоугольники будем хранить в множестве, упорядоченными по нижнему краю. Такое множество будем называть срезом. Для хранения множества можно использовать структуры данных, подобные красно-черным или декартовым деревьям или очереди с приоритетом. Нижний край нижнего прямоугольника будем называть краем среза. Если срез не содержит прямоугольников, то будем считать его край бесконечностью.

Так как при любом движении увеличивается координата времени, то будем рассматривать углы прямоугольников в порядке неубывания этой координаты. Рассматривая очередной угол, попытаемся двигаться от него по диагонали в обе стороны. Движение осуществляется по координатам, соответствующим границам прямоугольников. Достигая очередной координаты, проверяем, можно ли, двигаясь вертикально вверх, попасть в соответствующий верхний угол какого-либо прямоугольника. Достичь угол можно, если этот угол находится не выше края текущего среза. Также необходимо проверить, что движение не уперлось в край одного из прямоугольников, начинающихся в данной координате. Если удалось достигнуть координаты двери x, то необходимо обновить текущий ответ. Если при движении от одной координаты к другой был превышен край среза, то при переходе был достигнут нижний край прямоугольника, и движение необходимо прекратить.

Поочередно рассмотрев все углы и шагая в обе стороны от каждого из них, найдем минимальный возможный ответ или информацию о том, что дверь не достижима. Описанный алгоритм совершает O(n2 log n) операций, так как необходимо из каждого из O(n) углов пройти по диагонали O(n) различных координат и проверить O(n) прямоугольников. Также для каждого угла приходится совершать O(n log n) операций для поддержания среза, так как необходимо добавлять и удалять из среза O(n) прямоугольников.

Далее приведены возможные варианты прохождения мимо прямоугольников, которые необходимо не забыть обработать.

и

В то же время на следующем тесте невозможно успеть попасть к двери.

Эта задача тоже не из простых – ее решило всего 23 человека, первым – Куликов Егор на 100:18. Тут стоит отметить Епифанова Владислава, отправившего решение этой задачи, для него – последней, за 2 минуты до конца тура. Владислав занял первое место как в квалификации, так и на отборочном туре.

---

50 лучших из отборочного раунда перешли в финал. Он состоится 10 сентября в Swissotel, в Москве. Будет видеотрансляция, и, конечно, разбор задач и рассказ о финале после мероприятия.

Автор: raliev