606A - Магические сферы. Посчитаем, сколько сфер каждого типа недостаёт до цели. Нам надо провести по крайней мере столько преобразований. Посчитаем, сколько сфер каждого типа лишние по сравнению с целью. Каждые две лишние сферы дают нам возможность провести одно преобразование. Поэтому, чтобы понять, сколько преобразований можно сделать из данного вида сфер, надо посмотреть, сколько есть лишних сфер, поделить на 2 и округлить вниз. Сложим все возможности преобразований из каждого вида сфер и все недостачи. Если возможностей преобразований не меньше, чем недостач, ответ на задачу положительный. Иначе – отрицательный.

606B - Испытания роботов. Заведём матрицу, где для каждой клетки будем хранить, в какой момент робот впервые посещает её при прохождении маршрута. Чтобы найти эти величины, пройдём роботом весь маршрут. Каждый раз, когда приходим на клетку, в которой мы ещё не были, сохраняем в соответствующую ячейку матрицы, сколько сейчас сделано действий.

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

Теперь переберём все возможные клетки, где может находиться мина. Для каждой клетки, если она не посещена роботом, добавим одно прохождение из N действий, где N – длина маршрута. А если посещена, добавим одно прохождение из стольки действий, сколько написано в этой клетке (когда она была посещена). Ведь если мина в этой клетке, робот взорвётся сразу после первого её посещения. Массив счётчиков теперь – ответ на задачу.

605A - Сортировка вагонов. Предположим, мы убрали из массива те элементы, что будем переставлять. Что останется? Останется последовательность подряд идущих чисел: a, a+1, …, b. Длина такой последовательности должна быть максимальна, чтобы минимизировать число элементов, которые надо переставлять.

Рассмотрим массив pos, где pos[p[i]] = i. Посмотрим на его подотрезок pos[a], pos[a+1], …, pos[b]. Эта последовательность должна возрастать, а ее длина, как уже сказали выше, должна быть наибольшей. Таким образом, надо выделить наибольший подотрезок в массиве pos, где значения pos[a], pos[a+1], …, pos[b] идут в возрастающем порядке.

605B - Неуспевающий студент. Упорядочим рёбра по возрастанию длины, а при равенстве будем ставить раньше те рёбра, которые просят включить в MST. Начнем добавлять их в граф в этом порядке. Если текущее ребро просят включить в MST, соединим этим ребром 1-ю вершину с наименьшей изолированной пока ещё вершиной. Если текущее ребро просят НЕ включать в MST, соединим этим ребром две какие-то связанные ранее вершины, между которыми ещё нет ребра. Это удобно делать, поддерживая два указателя на вершины (назовём их from и to). Изначально from=2, to=3. Когда нам нужно соединить две связанные вершины, мы добавляем ребро (from, to) и увеличиваем from на 1. Если при этом from оказался равен to, мы делаем вывод, что мы уже добавили все возможные рёбра в вершину to, увеличиваем to на 1, а from устанавливаем на 2. Это значит, что с этого момента не-MST-шные рёбра мы будем проводить из to во все вершины начиная со второй. Если окажется, что to указывает на изолированную пока ещё вершину, мы можем сделать вывод, что в графе в настоящий момент нет места для не-MST-шного ребра и ответ Impossible. В итоге мы будем добавлять MST-шные ребра как (1,2), ..., (1,n), а не-MST-шные в порядке (2,3), (2,4), (3,4), (2,5), (3,5), (4,5), …

605C - Мечты фрилансера. Разрешим не получать денег или опыта за некоторые проекты. Добавление такой возможности не изменит ответ. Пусть герой потратил T времени на выполнение мечты. На каждый проект он потратил часть этого времени (возможно, нулевую). Тогда средняя скорость зарабатывания денег и опыта героем была линейной комбинацией скоростей зарабатывания на всех эти проектах, с весами равными долям времени, затрачиваемого на каждый из проектов.

Построим множество точек P на плоскости (x,y) таких, что мы можем получать x денег и y опыта в единицу времени. Расположим точки (a[i], b[i]) на плоскости. Добавим также точки (max(a[i]), 0) и (0, max(b[i])). Все эти точки точно принадлежат P. Найдём их выпуклую оболочку. После этого любая точка внутри или на границе выпуклой оболочки будет соответствовать использованию какой-то линейной комбинации проектов.

Теперь осталось выбрать точку, которую нужно использовать герою в качестве средней скорости зарабатывания денег и опыта за всё время реализации мечты. Она должна быть в пределах выпуклой оболочки. Мечта реализована, если мы придём в точку (A,B). Задача позволяет нам прийти правее или выше, но это сделать не проще чем прийти в саму точку (A,B). Поэтому направим в эту точку луч из (0,0) и найдём самый поздний момент, когда этот луч проходил по нашей выпуклой оболочке. Это будет соответствовать самой большой скорости набирания ресурсов, какую мы можем себе позволить в направлении точки (A,B). Координаты этой точки — это скорости, с которыми будут набираться ресурсы.

Чтобы найти саму точку, надо пересечь луч с выпуклой оболочкой.

605D - Настольная игра. Рассмотрим n векторов с началами в точках (a[i], b[i]) и концах в точках (c[i] и d[i]). Запустим поиск в ширину. На каждом его этапе нам необходимо выполнять такую операцию: получить множество векторов, у которых начало принадлежит прямоугольнику 0 <= x <= c[i], 0 <= y <= d[i], и больше не рассматривать эти векторы никогда. Это делается так. Сожмём координаты х. Для каждого x будем хранить список векторов, чья первая координата равна x. Заведем дерево отрезков, у которого индекс будет равен первой координате, а значение — второй координате. Дерево отрезков должно уметь находить индекс минимума на отрезке и проставлять значение в точке. Теперь пусть нам надо найти все векторы, у которых первая координата от 0 до x, а вторая от 0 до y. Найдем индекс минимума в дереве на отрезке [0, x]. Он укажет на вектор (x,y), у которого x — это тот самый индекс минимума, а y — значение минимума. Удалим его из списка векторов (добавив также в очередь поиска в ширину) и присвоим в дерево отрезков на этот индекс вторую координату следующего вектора с первой координатой x. Делаем так, пока минимум на отрезке все еще меньше y. Таким образом, на каждом шаге мы будем получать список еще не посещенных векторов в левом нижнем прямоугольнике, и каждый вектор будет получен ровно 1 раз, после чего он будет удален из структур данных.

605E - Межгалактические путешествия. Вершина тем более хорошая, чем меньше матожидание числа ходов из нее, чтобы добраться до финиша. В целом стратегия такова: если можно пойти в вершину, которая является более хорошей, чем текущая, то надо идти в нее, иначе оставаться на месте. Подобно алгоритму Дейкстры, будем хранить оценки ответа для каждой вершины, и фиксировать эти оценки как окончательный ответ в порядке от лучших вершин к худшим. На первом шаге мы зафиксируем вершину N (ответ для неё – 0). На втором шаге – вершину, из которой проще всего попасть в N. На третьем шаге – вершину, из которой проще всего закончить, переходя в вершины, определенные на первом и втором шагах. И так далее. На каждом шаге мы находим такую вершину, которая дает наилучшее матожидание числа ходов, если переходить из нее в вершины лучше нее, и фиксируем это матожидание – оно уже не может улучшиться.

Для каждой ещё незафиксированной вершины мы можем найти оценку, каково матожидание времени пути до финиша из неё. В этой оценке мы учитываем знание о вершинах, для которых ответ уже известен. Мы перебираем вершины в порядке неулучшения ответа для них, поэтому ответ для оцениваемой вершины не лучше, чем для уже перебранных. Посмотрим, как выглядит выражение для матожидания времени достижения финиша из вершины х, если пользоваться тактикой “идти в лучшую из i доступных вершин, для которых ответ уже известен, или стоять на месте”:

m(x) = p(x, v[0]) * ans(v[0]) + (1 — p(x, v[0]) * p(x, v[1]) * ans(v[1]) + (1 — p(x, v[0]) * (1 — p(x, v[1]) * p(x, v[2]) * ans(v[2]) + … + (1 — p(x, v[0]) * (1 — p(x, v[1]) * … * (1 — p(x, v[i-1]) * m(x) + 1

Здесь m(x) – оценка для вершины х, p(a,b) – вероятность существования ребра (a,b), а ans(v) – известный ответ для вершины v. Заметим, что m(x) выражается через себя, т.к. есть вероятность, что придётся остаться на месте.

Будем помнить оценочное выражение для каждой вершины в виде m(x) = A[x] * m(x) + B[x].

Для каждой вершины будем хранить A[x] и B[x]. Это будет значить, что с какими-то вероятностями удастся сдвинуться в более хорошую вершину, и эта возможность даёт вклад в матожидание B[x], а с какой-то вероятностью придётся оставаться на месте, и эта вероятность A[x] (она совпадает с коэффициентом перед m(x) в формуле).

Итак, на каждом шаге мы выбираем незафиксированную ещё вершину v с наименьшей оценкой, фиксируем её и производим релаксацию из неё, обновляя оценки для остальных вершин. Когда обновляется оценка для вершины x, мы изменяем её A[x] и B[x]. A[x] уменьшится на величину A[x] * p(x,v), т.к. вероятность, что придётся остаться на месте, подразумевает, что в вершину v тоже пойти не удалось. B[x] увеличится на величину A[x] * p(x,v) * ans(v), здесь A[x] – вероятность, что не удастся воспользоваться вершиной, более хорошей, чем v, A[x] * p(x,v) – вероятность, что при этом удастся воспользоваться вершиной v, а ans(v) – известный ответ, который мы только что зафиксировали для вершины v.

Чтобы посчитать, какова всё-таки оценка ответа для вершины, мы можем взять формулу m(x) = A[x] * m(x) + B[x] и выразить m(x). Именно m(x) нужно хранить в очереди с приоритетами для нашего аналога Дейкстры, и именно m(x) фиксируется как окончательный ответ для вершины х, когда она объявляется вершиной с наименьшей оценкой в начале шага.