344A - Магниты

По определению каждый островок состоит из последовательных одинаково направленных домино. Значит, в местах, где соседние домино направлены не одинаково, кончается один островок и начинается следующий. Значит, если таких мест x, то ответ равен x + 1.

Сложность решения O(n). Автор задачи: gen.

Бонус: Задача была придумана в день перед контестом и полностью дополнила физически направленный комплект для DivII :]

344B - Простые молекулы

Первое решение. Во-первых, заметим, что сумма a + b + c должна быть чётной, потому что каждое ребро прибавляет два к сумме. Теперь допустим, что между 1-ым и 2-ым, 2-ым и 3-им, 3-им и 1-ым атомами есть x, y и z связей, соответственно. Поэтому нам нужно решить систему x + z = a, y + x = b, z + y = c. Можно заметить, что решением этого уравнения являются длины касательных на треугольнике со сторонами a, b, c к его вписанной окружности, и равняются , , . Если бы в задаче просили проверить только, можно ли построить такую молекулу, то хватало бы проверить нестрогое неравенство треугольника для a, b, c.

Второе решение. Переберём значение x. Для него значения y и z определены однозначно: y = b - x, z = a - x.

Сложность решения O(1) / O(n). Авторы задачи: gen, andreyv.

Бонус: Можете ли вы решить задачу для произвольного n? Когда и как можно построить связный граф?

343A - Рациональное сопротивление

Если с помощью k элементов можем получить дроби , то нетрудно посчитать, что с помощью k + 1 элементов можно получить дроби и . То есть прибавление одного элемента эквивалентно одному шагу алгоритма Эвклида для числителя и знаменателя в обратном направлении. Значит, ответ равняется количеству шагов стандартного алгоритма Эвклида.

Сложность решения . Авторы задачи: gen, andreyv.

Бонус: Вначале мы думали об общей задаче (можно соединять два любых элемента, как многие неправильно поняли задачу), однако случился момент эврики, и мы поняли, что данная задача неожиданно естественно сводится к НОД. Кстати, дерево результатов – http://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree.

343B - Переменный ток

Вначале решим другую задачу: дана строка, состоящая из символов A и B. Если i-тый символ А, то на i-том шаге верхний провод (на рисунке) кладётся поверх нижнего. Если i-тый символ B, то нижний провод (на рисунке) кладётся поверх верхнего. Заметим, что если символ А стоит рядом с символом B, то эти два заплетания можно распутать и получить ситуацию, которую описывает та же строка, в которой выкинуты эти два символа. Поэтому провода можно распутать тогда и только тогда, если количество А совпадает с количеством В в этой строке. Нашу задачу мы можем свести к вышеописанной следующим образом: на каждой нечётной позиции заменяем – на B, а + на A. На чётных позициях заменяем – на A, а + на B. Можно видеть, что сведение правильное, потому что на каждой чётной позиции – и + всегда стоят перевернутые относительно начала, а на каждой нечётной порядок совпадает с порядком начала.

Сложность решения O(n). Авторы задачи: gen, andreyv.

Бонус: Если тема вас заинтересовала, можете ознакомиться с теорией кос http://en.wikipedia.org/wiki/Braid_theory :] Fun fact: усложнённый вариант задачи был предложен ещё на Round #142, но тогда в решении нашлась ошибка, и задача осталась лежать почти целый год.

343C - Время чтения

Будем искать ответ t двоичным поиском. Рассмотрим конкретное значение t. Рассмотрим первую головку слева h[i], которая может считать p[0]. Если p[0] > h[i], то h[i] просто идёт направо t секунд, и читает все дорожки на пути. Если p[0] ≤ h[i], то у головки есть два выбора:

1. идти направо секунд, затем налево и опять налево ещё h[i] - p[0] секунд;
2. идти налево h[i] - p[0] секунд, затем направо h[i] - p[0] и опять направо t - 2·(h[i] - p[0]) секунд.

Естественно, для h[i] выгоднее всего побывать в самой правой точке. Поэтому выбираем по . Дальше двигаем указатель на первую несчитанную дорожку, и повторяем алгоритм для h[i + 1], и.т.д. с каждой головкой.

Сложность решения . Авторы задачи: gen, gorbunov.

Бонус: Задача полностью реальна, если у диска есть только одна головка, и известно, какие данные нужно считать, то оптимальный алгоритм выбирает один из описанных двух вариантов. Это мы слушали на лекции вместе с gorbunov, и от скуки придумали такую задачу ;]

343D - Водяное дерево

Научимся быстро красить целое поддерево. Для этого пронумеруем все вершины в порядке выхода DFS. Тогда каждое поддерево покрывает один непрерывный отрезок номеров вершин. Для каждой вершины запомним границы такого отрезка для поддерева с корнем в этой вершине. Тогда красить поддерево означает покрасить отрезок в дереве отрезков.

Заведём дерево отрезков. Для него выполняется свойство: если вершина v была опустошена, и она до сир пор пуста, то эта вершина покрашена в дереве отрезков. В самом начале «опустошим» все вершины. То есть, покрасим все вершины в дереве отрезков. С помощью этого дерева можно эффективно обрабатывать запросы:

1. Заполняем вершину v. Стираем всё поддерево v в дереве отрезков. Если до этого поддерево не было пустым, то красим родителя v.

2. Опустошаем вершину v. Красим вершину v в дереве отрезков.

3. Отвечаем, заполнена ли вершина v. Если в дереве отрезков сумма поддерева v не равна 0, значит есть такой потомок v, который опустошён сейчас, поэтому вершина v не заполнена.

Идейно похожее, но более простое решение в написании предложил Shtrix.

Сложность решения . Автор задачи: gen.

Бонус: Некоторые участники могли заметить схожесть задачи с задачей Ball Machine из BOI 2013, однако решения этих задач имеют мало похожего.

343E - Насосные станции

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

Задача решается с помощью структуры данных дерево Гомори-Ху. Для данного взвешенного графа дерево обладает свойствами:

1. Множество вершин дерева совпадает с множеством вершин графа.
2. Максимальный поток в дереве между вершинами u и v равен максимальному потоку в графе между вершинами u и v.

Такое дерево на удивление существует для любого взвешенного графа и строится за время O(n·maxFlow). Оказывается, что для данной задачи ответом является сумма весов рёбер в таком дереве.

Докажем это утверждение индукцией по количеству вершин в дереве. Найдём ребро (u, v) с минимальным весом в дереве. Допустим, что для оптимальной перестановки вершин через это ребро проходит больше, чем один путь между парами соседних вершин в перестановке. Сотрём все такие пути, тогда в поддеревьях u и v остаётся в каждом по множеству несоединённых цепочек путей. Соединим все пути в каждом множестве в одну цепочку и получим две цепочки. Эти цепочки соединим одним путём s, который идёт через ребро (u, v). Получили перестановку, которая не хуже оптимальной. Для пути s ребро (u, v) является наименьшим, значит поток по этому пути равен весу этого ребра. Из индукции следует, что в поддеревьях u и v ответ равняется сумме ребёр. Добавляя к сумме вес ребра (u, v), получаем желаемое.

Из предыдущего абзаца ясно также, как строить такую перестановку: Берём наименьшее ребро, для поддеревьев вершин рекурсивно строим цепочки и соединяем их в одну. Так как вершин мало, эту часть можно делать даже за O(n²).

Сложность решения O(n·maxFlow). Авторы задачи: gen, Gerald.

Бонус: Ближе к соревнованию мы решили сделать ограничения лояльней, поэтому прошли также решения, которые O(n²) раз вызывают поток и затем строят дерево Гомори-Ху. Надеемся, этот факт никого особенно не огорчил. (;