Польша, Варшава, чемпионат мира по программированию.

Сегодня уже прошла регистрация участников, все заселились в один большой отель…

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

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

GoogleDoc

P.S.

1) Туда можно вписывать себя и знакомых.

2) Если кто-то не желает, чтобы о его местоположении знали, извините меня и просто удалите запись о себе.

3) Может, кто-то в комментариях расскажет, как такую инфу получать с официального сайта? :-)

В детстве мне очень нравилась задача 1147 с тимуса statements. Нравилась в первую очередь тем, что я знал кучу решений, но никак не мог придумать ни одного быстрее, чем за N². Сейчас у меня наконец появились мысли, как решать эту задачу за NlogN.

Обобщим сперва задачу, чтобы асимптотику оценивать только через N: пусть A, B < 10⁹, color < 10⁶

Я знаю следующие решения, все они используют сжатие координат:

1. Квадродерево за O(N²)

2. Решение одномерной задачи деревом отрезков за O(NlogN) => O(N² logN)

3. Решение одномерной задачи проходом слева направо с кучей за O(NlogN) => O(N² logN)

4. Решение одномерной задачи с помощью СНМ за O(N) => O(N²) [здесь в оценке я опускаю обратную функцию Аккермана]

5. Новое: Решение за O(NlogN) [использует разделяй и властвуй по X и сжатие координат при переходе к подзадаче].

Если кто-то знает что-то еще, расскажите, пожалуйста, в комментариях, мне это будет очень интересно :-)

Самое короткое и быстрое из того, что я сдавал на тимус — решение [4].

Решение [5] пришло в голову буквально только что..

Хочется его записать. Чтобы не забыть :-)

А всем, кто читает этот текст, предлагается проверить на наличие ошибок и понятность описания.

Решение:

1. Прямоугольник = отрезок [X1..X2] и операция на отрезке “присвоить отрезку [Y1..Y2] цвет C в момент времени T”.

2. У нас N прямоугольников, значит, после сжатия координат у нас не более 2N элементарных промежутков по X и по Y. Обозначим количество различных X-ов за M. Для всех M различных X-ов мы хотим получить раскраску столбца (вернее посчитать количества цветов).

3. Используем идею разделяй и властвуй, обработаем сперва первую половину X-ов, затем вторую. Алгоритм = рекурсивная функция go.

4. Общее состояние рекурсии: go( [xL..xR], column, rectangles ). [xL..xR] — отрезок X-ов, который мы сейчас обрабатываем, column — текущая раскраска всей полоски [xL..xR], rectangles — запросы-прямоугольники, которые я еще не обработал. Изначально [xL..xR] = [0..M-1], column = [0,0,0 … 0], rectangles = все запросы.

5. Первым делом “go” разбивает rectangles на 3 группы: “не пересекается с [xL..xR]”, “целиком покрывает [xL..xR]”, “пересекает [xL..xR]”. 1-ю группу можно выкинуть. 2-й группой перекрасить как-то column. А 3-ю группу будем передавать вниз в рекурсию.

6. Второе, что делает “go”: сжатие координат. Да, каждый раз происходит новое сжатие координат.

7. За [5] и [6] я добился того, что column состоит из O(Len) элементарных клеток, и массив rectangles содержит O(Len) элементов, где Len — длина отрезка [xL..xR]. Теперь можно сделать два рекурсивных вызова. Решение закончилось.

8. Оценим время работы: T(K) = T(K/2) + T(K/2) + [5-перекрасить] + [6-сжатие-координат]. Если все координаты у меня от 0 до K-1, то сжатие координат работает за O(K). [5-перекрасить] — перекрашивание массива column, этим я занимаюсь в пункте [5]. По сути это решение одномерной задачи (см. список решений одномерной задачи). Используя СНМ, я получаю время O(Kα), где α — обратная функция Аккерамана. Итого: T(K) = 2T(K/2) + O(Kα). T(K) = O(KlogKα).

P.S. Это решение просто переиспользует все ту же мою любимую идею из dynamic-connectivity

UPD1: Михаил Колупаев верно подсказывает, что в [7] ошибка. Правильная версия такова: количество элементарных клеток = O(rectangles), а суммарное количество rectangles по всем 2M состояниям рекурсии = O(NlogN), т.к. каждый прямоугольник также, как и в дереве отрезков, присутствует только в O(logN) вершинах.

UPD2: Ошибка Я попробовал это все реализовать. Выяснилась отличная ошибка. В [6] сжатие координат не работает, т.к. уже покрашенная область имеет дурацкое свойство — у каждой клетки свое время покраски. Итог: алгоритма работающего за NlogN таки нет =((( у меня осталась только старая, уже проверенная идея, за Nlog³N.

164A - Переменная, или Туда и обратно

Кратко о решении — dfs, O(E).

Пустим поиск в глубину из всех вершин, где переменная присваивается. Пометим все посещенные.

Пустим поиск в глубину по обратным ребрам из всех вершин, где переменная используется. Запретим ему проходить по вершинам, где переменная присваивается. Пометим все посещенные.

Вершины помеченные оба раза — это и есть те вершины, где состояние Васи кого-то волнует

164B - Древние берляндские иероглифы

Кратко о решении — метод двух указателей, O(N).

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

Тогда у нас есть перестановка p_i (позиция во второй строке i-го символа первой строки)

Решение за квадрат теперь такое: фиксируем начало подстроки и идем по ней вперед, при этом параллельно идем по подпоследовательности и следим, что и там, и там мы не прошли больше круга.

Решение за линию.

Будем теперь идти двумя указателями “начало подстроки” и “конец подстроки”. Параллельно будем хранить очередь — текущая парная подпоследовательность. В очереди все p_i обязательно возрастают (этого не сложно достичь, т.к. можно прибавлять к p_i число n столько раз, сколько нужно. То что подпоследовательность не зациклилась проверяется так queue.first - queue.last < n. Значит, мы можем двигать конец подстроки вперед, пока это неравенство выполнено. Как только конец подстроки нельзя увеличить, увеличиваем начало. Заметим, что начало и конец подстроки также двигаются по кругу.

Альтернативное решение:

После того, как мы увидели перестановку p, можно воспользоваться методом двоичных подъемов и получить решение за O(NlogN), которое тоже получало Accepted.

164C - Автоматное программирование

Кратко о решении — MinCost flow, O(N² K) или O(NlogN K).

Самое главное было — увидеть граф, где вершины = задания, множества заданий, выполняемые автоматами = вершиннонепересекающиеся пути, а ребра можно было строить двумя способами (см. ниже).

Как сделать пути вершиннонепересекающимися? Раздвоить вершины.

Как добавить стоимость? Между двумя половинками вершины должна быть стоимость  - c_i.

Первый способ, граф G₁ : вершины A, B соединены ребром, если после задания A можно успеть выполнить задание B тем же автоматом. Тогда ребер O(N²).

Второй способ, граф G₂ : все вершины упорядочены по s_i из вершины i ведут два ребра — в i + 1 (не берем i задание, пробуем взять следующее) и в вершину с минимальным j : s_j ≥ s_i + t_i (берем задание, переходим к минимальному из возможных следующих). Тогда ребер O(N).

Если вы пользовались первым способом и для поиска пути реализовали одну из вариаций алгоритма Форда-Беллмана, то вы могли получить TL. Собственно пока из-за того, что на java все медленно, TL не подняли, все Форд-Беллманы кроме одного особенного получали заслуженный TL.

Чтобы в G₁ использовать Дейкстру с потенциалами, удобнее всего было заметить, что граф ацикличен и первый раз расстояния посчитать за O(E).

164D - Минимальный диаметр

Кратко о решении — бинпоиск по ответу, а внутри перебор за O(Fib(K)).

Правильное решение состояло из четырех несложных идей:

1) Нужно из N² ребер покрыть удаленными вершинами сколько то максимальных. Когда мы покрываем еще не покрытое ребро, у нас 2 варианта это сделать — выбрать 1 конец, выбрать второй конец. Эта идея сама по себе давала асимптотику O(2^K * N).

2) Если сделать бинпоиск по ответу, то мы решаем более простую задачу: можно ли покрыть первые X ребер K вершинами? Т.е. правда ли, что размер контролирующего множества в таком графе не более K.

3) Если мы теперь внутри бинпоиска не берем какую-то вершину, то мы должны брать всех ее соседей в уменьшенном графе. Из этого можно сделать 2 вывода: во-первых, если есть вершина степени больше чем K, ее брать обязательно, во-вторых, не выгодно брать вершину степени 1.

4) Теперь решение работает за log * Fib(K) * K, где log — константа от бинпоиска, Fib(K) — K-е число Фибоначчи, K — максимальная степень вершины в уменьшенном графе.

Почему Fib(K)? Теперь, когда мы делаем выбор, в одной ветке рекурсии K уменьшается на 1, а в другой хотя бы на 2… На лицо числа Фибоначчи.

P.S. Из похожих задач я знаю вот эту: задача 2 с РОИ 2009-2010

164E - Поликарп и работы

Кратко о решении — жадность + куча запросов на отрезке, асимптотика = O(NlogN).

В этой задаче так и не получилось написать очевидное условие…

Расскажу некоторую легенду, чтобы дать понять, что задачка не искусственна, взята из “реальной жизни”.

Все вы читали задачу C. Давайте чуть поменяем ее, скажем, что автомат у нас один, а работа должна начаться не раньше l_i, закончиться на позже r_i, а времени на нее уйдет t_i. Рассмотрим случай, когда l_i и r_i возрастают.

Попробуем придумать жадное решение: отсортируем все работы по l_i и будем пытаться “брать”. Если можно взять, то выполнять работу будем в минимально возможный момент времени.

Это жадное решение не сложно завалить тестом (L=1, R=10, T=10), (L=2,R=11,T=5), (L=3,R=12,T=5).

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

Собственно задача E состояла в моделировании процесса. В том, чтобы запрограммировать эту жадность.

Итак, решение:

Для каждого отрезка определим величину shift_i = s_i — l_i (насколько можно отрезок подвинуть влево).

У нас уже есть k отрезков. Добавляем k + 1-й, не получается. Пробуем сделать замену. Перебираем все отрезки в порядке уменьшения индекса, смотрим, насколько уменьшится правый конец.

Это min(t_i, min по j=i+1..k (shift_j)).

Т.е. ни один из отрезков из 1..i уже не даст ответ лучше, чем min(max по j=i+1..k (t_j), min по j=i+1..k (shift_j)).

Зачем я выдумал этот максимум? Дело в том, что под минимумом теперь две функции, убывающая и возрастающая. Значит, максимум можно искать бинарным или троичным поиском.

Следующая идея заключается в том, что когда мы нашли оптимальную замену besti, то чтобы пересчитать все shift_j, достаточно сделать вычитание на отрезке besti+1..k

Полученное решение имеет асимптотику O(Nlog²N). Его можно улучшить до O(NlogN), заменив бинпоиск, а внутри него обращение к дереву поиска или дереву отрезков на один спуск по дереву.

UPD:

По просьбам участников выкладываю “разбор” задач A,B,C второго дивизиона.

Задачи второго дивизиона я не готовил, не читал, не решал. Но вроде бы, если почитать, они решаются так, как описано ниже. Так что разбор второго дивизиона не стоит воспринимать как авторский, это просто рассказ “как бы я решал эти задачки”. Надеюсь, нигде не наврал.

Задача A

X = (a₁ + a₂ + … + a_n + b) / n.

Если X меньше максимального a_i, то нельзя сделать так, как просят. Иначе нужно вывести числа X — a_i.

Задача B

Решение #1, жадное:

Если между двумя точками больше 11 или меньше 2 символов, то нельзя так разрезать.

Если перед первой точкой больше 8 символов, то нельзя так разрезать.

Если между после последней точки больше 3 символов, то нельзя так разрезать.

А иначе режем жадно :-) Если количество символов между двумя точками равно X, то разрез проводится в позиции min(8,X-1).

Решение #2, DP:

is[i] — можем ли мы разрезать префикс длины i.

Изначально is[0] = 1, остальные нули.

Теперь перебираем i в порядке возрастания и если is[i] = 1, пытаемся сделать переход в i + 1..i + 12.

Задача C

Основная идея — жадность.

Если минимум на всем массиве равен нулю, то задача естественным образом распадается на подзадачи, а иначе нужно уменьшить весь отрезок на 1.

Решение #1, ищем минимум

Ищем минимум в массиве, вычитаем 1 из всего массива min раз, задача распадается на несколько (т.е. в каждый момент времени, задача = отрезок исходного массива). Минимум на отрезке нужно искать быстро, за O(logN), например.

Решение #2, простое

Будем идти слева направо и хранить, сколько у нас отрезков уже начато торчит налево, пусть это X. Если X < a_i, то нужно начать несколько новых отрезков, если же X > a_i, то несколько уже начатых нужно закончить в позиции i - 1. Начатые отрезки можно хранить в стэке. Хранить, конечно, нужно только позицию начала. Новый X будет равен a_i.

Конец.

Здравствуйте!

Сегодня, 8-го апреля, состоится последний 3-й отборочный раунд VK Cup 2012. Напоминаем, что регистрация на этот раунд также необходима и завершается она за пять минут до начала.

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

Над задачами работал разнообразный коллектив авторов как со стороны ВКонтакте, так со стороны Codeforces и Саратовского государственного университета.

Мы постарались сделать задачи сложнее, чем обычно, но все же решаемыми за положенные 2 часа. Надеемся, участие в раунде доставит вам удовольствие, а в финал пройдут сильнейшие.

Раунд пройдёт по правилам Codeforces: с распределением на комнаты, со взломами и с обычным падением стоимости задач со временем. Раунд будет рейтинговым как если вы участвуете в чемпионате, так и если вы пишете вне него.

Из всех участников первые 50 пройдут в финальный раунд, который состоится в июле в Санкт-Петербурге.

Пожалуйста, чтобы раунд для вас был еще интереснее, прочитайте условия ВСЕХ задач.

Успехов!

UPD1:

В редакции для Див. 2 будет использована динамическая сложность задач http://codeforces.ru/blog/entry/4172. Задачи будут упорядочены по возрастанию предполагаемой сложности, но баллы за них будут определятся на основании доли решивших их.

UPD2

Доступен разбор: Разбор

** UPD : Считается, что все формулы уже исправлены **

163A - Подстрока и подпоследовательность

Кратко о решении: динамика.

Одно из авторских решений: 1415300 (автор = levlam)

Задача решалась следующей динамикой. Пусть f[i, j] — количество равных пар вида “подстрока начинающаяся в позиции i” и “подпоследовательность подстроки t[j..|t|]”.

Тогда:

f[i, j] = f[i, j + 1];
if (s[i] == t[j])
  add(f[i, j], f[i + 1, j + 1] + 1)

Answer = f[i,0]

163B - Лемминги

Кратко о решении: сортировка + бинпоиск по ответу.

Одно из авторских решений: 1415306 (автор: Burunduk1)

Нам нужно найти минимальное время T. Давайте сделаем бинарный поиск по ответу.

После этого можно расставлять леммингов жадно или снизу вверх, или сверху вниз. В этом разборе я воспользуюсь способом <снизу вверх>. Из тех леммингов, которые могут забраться на 1-й уступ, выберем лемминга с минимальной массой, а из таких — с минимальной скоростью. Почему так можно сделать? Пусть мы поставили на первый уступ лемминга с большой массой, значит, всех леммингов с меньшей массой мы использовать уже не можем, значит, можно было поставить на первый уступ любого лемминга с меньшей массой. А из леммингов с одинаковой массой всегда выгодно оставить тех, чья скорость больше, они могут залезть на более высокие уступы.

Чтобы быстро расставлять леммингов в таком порядке, отсортируем их заранее, сравнивая сперва по массе, затем по скорости. После этого мы рассматриваем всех леммингов в порядке возрастания массы ровно один раз и каждого или берем, или не берем. Второй раз рассматривать лемминга не имеет смысла, т.к. или мы его уже взяли на i-й уступ (он занят) или мы его на i-й уступ взять не смогли, тогда на i + 1-й и т.д. тоже не сможем.

Итого решение = сортировка + бинпоиск по ответу с линейным проходом внутри. Время работы = O(Nlog?)

Но написать бинпоиск и верную жадность в этой задаче было не достаточно для получения Accepted. Нужно было еще не попасться на проблемы с точностью. Давайте точно оценим число итераций бинпоиска.

0 ≤ T ≤ H * K (максимальное время не больше 10⁹). Нужно понять, насколько могут отличаться два времени. В случае “N = K = 10⁵, H = 10⁴, V порядка 10⁹” времена, за которые некоторые два лемминга поднимаются на какие-то уступы, могут отличаться на 10^- 18. Это следует из того, что времена = рациональные дроби , где X и Y порядка 10⁹.

Т.е. нам нужно сделать число итераций = log₂10²⁷ = 90. На практике моему решению 70 итераций не хватало, а вот 75 было уже достаточно. Рассуждения выше показывают, что 90 точно хватит.

163C - Конвейер

Кратко о решении: события на окружности или бинпоиск.

Одно из авторских решений: 1415310 (автор: Burunduk1)

Одно из авторских решений: 1415316 (автор: arseny30)

Антон, откуда бы он ни начал, пробежит по конвейеру отрезок длины D = (v₂  l) / (v₁ + v₂). Рассмотрим одну конфету. Чтобы ее скушать, нужно попасть на конвейер в любой момент из отрезка [ a_i — D .. a_i ]. Рассмотрим все точки вида a[i] — D и a[i] , если какие-то из них отрицательны, прибавим 2  l. Также не забудем добавить в массив точек числа 0 и 2 * l. Отсортируем эти точки. Рассмотрим теперь две соседние — x[i] и x[i+1]. В какой бы момент времени между этими двумя точками Антон ни начал, он съест одно и то же количество конфет.

С этого момента можно получить одно из двух решений:

1) Запуститься от каждой середины отрезка M = (x[i] + x[i+1]) / 2 и бинпоиском по отсортированному удвоенному массиву a найти количество конфет на отрезке [M..M + D].

2) Сказать, что у нас есть события на окружности вида (a[i]-D,+1) и (a[i],-1). Нужно пройти по кругу два раза, и на втором проходе говорить, что мы знаем, сколько раз покрыт текущая точка конфетами-отрезками.

Оба решения работают за время O(NlogN).

163D - Большой холодильник

Кратко о решении: перебор с отсечением по ответу

Одно из авторских решений: 1415320 (автор: Burunduk1)

Решение состоит из трех главных идей:

1. V = ABC, A ≤ B ≤ C тогда A ≤ N^1 / 3, B ≤ (N / A)^1 / 2.

2. A и B — делители V, а поскольку нам уже дано разложение числа V на простые множители, можно перебирать только делители

3. Если зафиксировано A, то оптимальные вещественные B и C = (N / A)^1 / 2 (обозначим эту величину за X). Т.е. площадь поверхности получится в любом случае  ≥ 2(2AX + X²). Таким образом можно использовать отсечение по ответу.

Если применение в лоб этих идей давало TL, то можно было воспользоваться следующими оптимизациями:

1. Отсечение по ответу лучше работает, если перебирать A в порядке убывания

2. A и B — 32-битные целые.

3. Если мы для числа V уже считали ответ, то нужно запомнить ответ (таким образом мы чуть уменьшили max тест).

Если кому-то интересно теоретическое обоснование “Почему это все работает за нужное время?”, приведу некоторую статистику:

1. Максимальное количество делителей у чисел от 1 до 10¹⁸ = 103860 (у числа 897612484786617600 = 2⁸3⁴5²7²11 …)

2. Если использовать только 2 первые оптимизации, количество чисел A, которое переберет наше решение = 10471 (на числе с max количеством делителей)

3. Если использовать только 2 первые оптимизации, количество пар A и B, которое переберет наше решение = 128264 (на числе с max количеством делителей).

163E - Электронное правительство

Кратко о решении: Ахо-Корасик + сумма на пути в дереве суффиксных ссылок

Одно из авторских решений: 1415345 (автор: arseny30)

Предполагается, что читатель знаком с алгоритмом Ахо-Корасик (прочитать о нем можно здесь http://e-maxx.ru/algo/aho_corasick).

Пусть у нас есть бор имен и суффиксные ссылки на этом боре. Также для каждой вершины v посчитано количество имен, кончающихся в этой вершине (end[v]).

Тогда добавить имя i: end[v[i]] += 1, где v[i] — вершина-конец i-го имени

Удалить имя i: end[v[i]] -= 1.

Чтобы ответить на запрос “политизированность текста”, нужно увидеть, что суффиксные ссылки образуют дерево. Когда мы проходимся по тексту и параллельно ходим по бору с суффиксными ссылками, если мы находимся в вершине бора v, нужно прибавить к политизированности сумму end[v[i]] на пути по суффиксным ссылкам от v до корня дерева. Теперь нужно научиться быстро решать задачу <сумма весов вершин на пути до корня, веса меняются>.

Это можно сделать например так:

1. Говорим, что вес не в вершине, а на ребре, соединяющем вершину с ее отцом.

2. Храним Эйлеров обход дерева, в котором при спуске вниз записан плюс вес ребра, а при подъеме наверх минус вес ребра.

3. Сумма на пути до корня = сумма на отрезке в Эйлеровом обходе (концы отрезка — произвольные вхождения двух вершин в Эйлеров обход).

Быстрый и удобный способ считать сумму на отрезке — дерево Фенвика.

Мы получили решение работающее за время O(|SumLen| * log). Памяти используется |SumLen| * 26 (бор мы храним не сжатым).

Здравствуйте!

Пришла пора второго раунда нашего соревнования VK Cup 2012. Напоминаем, что регистрация на этот раунд также необходима и завершается она за пять минут до начала.

Над задачами работал разнообразный коллектив авторов как со стороны ВКонтакте, так со стороны Codeforces и Саратовского государственного университета.

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

Раунд пройдёт по правилам Codeforces: с распределением на комнаты, со взломами и с обычным падением стоимости задач со временем. Раунд будет рейтинговым как если вы участвуете в чемпионате, так и если вы пишете вне него.

Из всех участников первые 175 пройдут в третий раунд сразу же. Ещё 25 участников смогут выйти в третий раунд через второй Wildcard-раунд, который состоится 28 марта и представляет из себя одну задачу с неточным решением.

Пожалуйста, чтобы раунд для вас был еще интереснее, прочитайте условия ВСЕХ задач.

Успехов!

UPD1: Опубликован разбор задач: http://codeforces.ru/blog/entry/4187

Мне очень интересно, умеют ли сейчас люди решать вот такую задачу (я приведу сперва основную идею, а потом несколько вариаций условия):

Дана плоскость т.е. бесконечный грид точек с целыми координатами. На плоскость упали по очереди N прямоугольников (по очереди, значит, порядок важен) со сторонами параллельными осям координат и значением value_i внутри. Для всех точек, покрытых прямоугольником, нужно сделать некоторую операцию с value_i. После этого вам поступают K запросов вида “посчитайте что-нибудь на прямоугольнике”.

Предполагается, что структуру данных для N прямоугольников можно строить в Offline, а вот на запросы нужно отвечать в Online.

1. операция +=, запрос сумма
2. операция +=, запрос минимум
3. операция присваивание, запрос сумма
4. операция присваивание, запрос минимум

Утверждается, что я умею решать все 4 задачи за следующее время:

1. Time = Nlog, Memory = Nlog, AnswerQuery = log
2. Time = Nlog², Memory = Nlog², AnswerQuery = log
3. Time = Nlog², Memory = Nlog, AnswerQuery = log
4. Time = Nlog³, Memory = Nlog², AnswerQuery = log

Краткое описание решений:

1. 1-я задача: Scanline + Persistent Дерево Отрезков
2. 2-я задача: Давайте для каждого K для каждого X-а предподсчитаем дерево отрезков по Y для полоски [X..X+2^K) делается это опять же ScanLine-ом с Persistent Деревом Отрезков.
3. 3-я задача: Scanline + Persistent Дерево Отрезков, при этом на дереве отрезков операция сложнее. Нужно добавлять и удалять информацию вида “на отрезок [L..R] в момент времени t кто-то упал”, и, считая сумму на отрезке, выбирать последнее по t событие для каждой точки. Утверждается (1) если нет удаления, добавлять не трудно, (2) удалять не нужно. От удаления я избавляюсь также, как и в Dynamic-Connectivity в Offline, далее ссылка на условие задачи: http://195.19.228.2//download/codeforces/connect.pdf
4. 4-я задача: 2+3

UPD про задачи (2 и 3):

Я извиняюсь перед теми, кто видел первую версию поста. “Краткие решения” к задачам 2 и 3 были перепутаны местами =(

Друзья, будьте бдительны!

Алгоритм Левита взятый с http://e-maxx.ru/algo/levit_algorithm работает в худшем случае за экспоненциальное время.

Для пояснения привожу код, который генерирует ацикличный граф без отрицательных ребер из 91 вершин и 121 ребра (а также перемешивает все ребра в случайном порядке), на котором код по ссылке выше делает более 1 000 000 добавлений в очередь.

const int M = 30;
const int W = (int)8e8;

void gen()
{
  for (int i = 0; i < M; i++) 
    g[i].push_back(make_pair(i + 1, 0));
  g[0].push_back(make_pair(M, W));
  n = M;

  for (int i = 0; i < M; i++) 
  {
    g[n].push_back(make_pair(n + 2, W >> i));
    g[n].push_back(make_pair(n + 1, 0));
    g[n + 1].push_back(make_pair(n + 2, 0));
    n += 2;
  }
  n++;
  for (int i = 0; i < n; i++) 
    random_shuffle(g[i].begin(), g[i].end());
}

Друзья, а где-нибудь есть официальный список открытых тренировочных контестов?

Имеются в виду списки по типу тех, что я нашел
для http://acm.math.spbu.ru:8087/~ejudge/team.cgi?contest_id=
http://pastie.org/2711469
http://acm.math.spbu.ru/~sk1/download/codeforces/snarknews.txt
и для http://158.250.33.215/~ejudge/team.cgi?contest_id=
http://udalov.org/opencup

...только полученные не циклом for, а более-менее официальные и online обновляющиеся.

UPD: Саша Удалов подсказывает, что на http://udalov.org/opencup контесты с обоих серверов, да еще и только те, куда точно можно войти, используя логин-пароль с кубка.