195A - Посмотрим футбол

Полное видео скачается через all = (c·a + b - 1) / b секунд. В этой задаче можно было перебрать величину ответа 1 <  = t <  = all. Чтобы удовлетворить условию задачи, достаточно проверить, что в последний момент времени t0 = all выполняется условие, написанное в тексте задачи, а именно t0·b >  = (t0 - t)·a.

195B - После тренировки

В этой задаче нужно было аккуратно реализовать описанный в условии процесс. Вначале заметим, что мяч с номером i > m попадет в одну корзину с мячом под номером i - m. Поэтому достаточно распределить первые m мячей. Это удобно сделать при помощи двух указателей lf, rg, начиная с середины. Поочередно кладем мяч сначала слева, затем справа и двигаем указатели. Единственный раз, когда нужно дважды подвинуть левый указателей, возникает в самый первый момент, если m нечетно.

195C - Попробуй поймай

Данная задача носила реализационный характер. В своем решении я поступал следующим образом. Удалим из текста все пробелы, кроме пробелов в сообщениях try-catch блоков. Затем при появлении слова try, кладем номер нового try-catch блока в стек. При появлени слова throw, запомним его тип, а также текущее состояние стека (то есть какие try-catch блоки открыты). Для этого, например, положим номера открытых блоков в set. При появлении слова catch, если тип блока совпадает с типом оператора throw, а также номер текущего блока находился в стеке при появлении оператора throw (то есть он есть в нашем set-е), то сразу выводим ответ. Иначе удаляем текущий try-catch блок из стека. Если подходящего try-catch блока так и не найдется, в конце выводим фразу "Unhandled Exception".

195D - Исследование ломаной

Разбор от автора Igor_Kudryashov

В данной задаче были заданы по сути прямые в виде y_i = k_i * x + b_i, но в тех точках, где y принимает отрицательное значение, оно заменено нулем. Необходимо было найти количество углов, не равных 180 градусам, в графике функции, равной сумме функций указанного вида.

Во-первых, несложно показать, что сумма прямых является прямой. В самом деле, если y = y₁ + y₂, то y = k₁ * x + b₁ + k₂ * x + b₂ = (k₁ + k₂) * x + (b₁ + b₂). Рассмотрим точки, в которых y_i = 0, т.е. x_i =  - b_i / k_i. Пока предположим, что k_i не равно 0. Тогда i-ая функция разбивается на две прямые, одна из которых тождественно равна 0. Оставим среди x_i различные точки и упорядочим их по возрастанию значения. Тогда, очевидно, между двумя соседними точками суммой заданных функций является прямая. Найдем уравнение этой прямой. Предположим, мы рассматриваем i-ую слева точку. Тогда если уравнение прямой между i-ой и (i + 1)-ой точками, отлично от уравнения прямой между (i - 1)-ой и i-ой точками, тогда в i-ой точке образуется угол, не равный 180 градусам.

Таким образом, нам необходимо найти уравнение прямых на отрезках между соседними точками x, т.е. найти коэффициенты k и b. Это можно легко сделать с использованием 2 массивов запросами увеличения на отрезке в оффлайне.

Когда мы обрабатываем очередную функцию, мы смотрим, если k_i равно 0, то нужно ко всем отрезкам прибавить одну и ту же величину, но т.к. данное изменение не повлияет на ответ, то можно не обрабатывать функции такого вида. Если k_i не равно 0, то найдем индекс j точки x_i в упорядоченном списке x. Теперь если k_i больше 0, то нужно сделать увеличение на суффиксе, начиная с позиции j, иначе нужно сделать увеличение на префиксе до позиции j (при этом увеличение на префиксе коэффициента k будет производиться на отрицательную величину).

195E - Построение леса

Разбор от автора Fefer_Ivan

В этой задаче самой долгой операцией является поиск корня вершины и длина пути до него. Эту операцию можно выполнять быстро используя эвристику сжатия путей. Такой же метод применяется в структуре данных Disjoint Set Union.

Для каждой вершины v мы будем хранить два числа: c[v] и sum[v]. c[v] = v, если v — корень, иначе c[v] — следующая вершина на пути от v к корню. sum[v] = сумме длин ребер на пути от v до c[v].

Таким образом для того, чтобы добавить ребро из u в v веса w, достаточно c[u] = v, а sum[u] = w. Теперь мы можем за O(n) находить по вершине нужные нам в задаче root(v) и depth(v) просто переходя каждый раз из v в c[v] и суммируя все sum[v] по пути.

Заметим, что мы только добавляем ребра, но не удаляем. Это значит, что если мы для вершины v нашли root(v) и depth(v), то можно присвоить c[v] = root(v), sum[v] = depth(v). Таким образом в следующий раз мы найдем предка вершины v за О(1). В общем реализация этого подхода выглядит следующим образом:

int root(int v){  
   if(c[v] == v){  
       return v;  
   }else{  
       int u = root(c[v]);  
       sum[v] = (sum[c[v]] + sum[v]) % M;  
       c[v] = u;  
       return u;  
   }  
}  

Доказывается, что такая реализация работает в сумме за время, пропроциональное обратной фунции Аккермана http://en.wikipedia.org/wiki/Ackermann_function#Inverse) на запрос при применении ранговой эвристики. Поскольку в этом случае нельзя её применить, то такой запрос обрабатывается за log(n). Итого получаем решение за время O(n * log * (n)).