TL 12 107676717 -- unordered_map<int, int> cnt (TL = 2s)
TL 18 107676732 -- unordered_map<int, int> cnt(n) (works 46ms on 12th test)
OK 107676952 -- sort (works 77ms and 66ms on 12th and 18th tests)

What's going on?) I have no access to tests and can not repeat this effect locally (both windows:g++, linux:g++)

UPD:
107679200 rehash(100 + gen() % 10000) gives OK in 670 ms, which is still too slow
107679288 rehash(100 + gen() % 10000) + reserve gives OK in 100 ms, which is strange but acceptable.

PS:
This comment says "anti-hash test". I also have only this idea.
This comment gives more precise answer.
In future of course i will just use my own hash-table with no such faults.

PPS:

Both constructor(x) and rehash(x) seems to set bucket_count to minimal prime $$$\ge$$$ x, so we can still use unordered_map in one of two following ways:

mt19937 gen(time(NULL));
unordered_map<int, int> cnt;
cnt.rehash(n + gen() % n);

mt19937 gen(time(NULL));
unordered_map<int, int> cnt(n + gen() % n);

Хочу понять, как запускать dfs на java, чтобы он работал быстро. $$$n = 2\,300\,000$$$.

Сабмит 54911336, говорит, что codeforces (windows, java32 1.8.0_162) даёт time in dfs = 126ms.

У меня локально (windows, java64 11.0.1) time in dfs = 13913ms. Разница в 100 раз!

У Petr (windows, java 1.8.0_181) 15 секунд.

Ключи запуска java -XX:NewRatio=5 -Xms8M -Xmx512M -Xss64M брал отсюда.

Ребят, у кого сколько работает? (интересно время, os/проц, версия java, ключи запуска)

Как добиться 126ms локально?)

UPD:
У меня локально добавление -XX:TieredStopAtLevel=1 (help) даёт 387ms.
Опции "ровно как на codeforces" локально на java64 работают те же 13913ms $$$\pm\varepsilon$$$. То есть, важно что на cf именно java32.

Предыстория

Жил был алгоритм Форд-Беллмана. Разные люди его по-всякому оптимизировали.
Например, популярен «Форд-Белман с очередью», также известный, как SPFA.

Здесь мы рассмотрим менее популярную версию «Форд-Белман с random shuffle».

(1) random_shuffle(edges.begin(), edges.end());
for (int run = 1; run; ) {
	run = 0;
        (2) random_shuffle(edges.begin(), edges.end());
	for (Edge e : edges)
		if (relax(e))
			run = 1;
}

Фазой назовём цикл по всем рёбрам. Обычный Форд-Беллман сделает не более V фаз.

История

Оказывается, от того, где написать random_shuffle,
сделать один раз заранее, или делать в начале каждой фазы, многое зависит.

На худшем тесте матожидание числа фаз у одного из новых Форд-Беллманов равно V / 2, у другого V / 1.72.
Как думаете, у кого меньше? Скоро допишу сюда ответ и доказательства.

Если вы любите математику, но не Форд-Беллмана, вот теорвер-составляющая

int i = 0, phase = 0;
p = [0, 1, ... n-1]
(1) random_shuffle(p.begin(), p.end()); 
for (int i = 0; i < n; phase++) {
	(2) random_shuffle(p.begin(), p.end()); 
	for (int x : p)
		if (x == i)
			i++;
}
// Найти матожидание phase в зависимости от того, где random_shuffle, в (1) или (2).

UPD: правильный ответ и доказательства записал eatmore, спасибо ему.

Привет.

Есть такой старый старый и очень любимый мной уральский сайт с задачками: timus

Он уже пару дней как пингуется, но не открывается. Скажите, кто знает, как он там?

UPD: Спасибо, Len. В соседнем топике говорят, что есть зеркало.

Всем хорошего настроения.

Я заметил, что умею из дерева отрезков с реализацией сверху на массиве [0..n) получать его динамическую версию для интервала [0..INT_MAX) изменением всего пары строк: (simple) (dynamic)

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

Сегодня опять получил письмо от CF, где написано по-английски про новый раунд "Monday, October, 12, 2015 09:00 (UTC)."

Как сделать так, чтобы CF догадался, что я живу в Питере? Или всем приходит время в UTC?

Помните? http://codeforces.me/contest/513/standings

Сейчас позвонили из компании UPS, говорят, на таможне лежит моя футболка с рокетона, нужно выслать им копию паспорта и "подтверждающие документы".

Что это? У вас было так? У меня первый раз.

Так и должно быть? Если да, rocketfuel, это полный упс!

Добрый день.

Это пост о мелочах в реализации хешей.

Сегодня ребята гуглили "как писать полиномиальные хеши", но нагулили лишь две ссылки на тему "как не надо писать полиномиальные хеши" — e-maxx и habr.

А можно писать иначе — short и full. Последняя версия устойчива к антихеш тестам, её можно копипастить.

Теперь подробно. Есть два способа. Оба для краткости будут написаны по модулю 2⁶⁴, то есть падают на строке Туе-Морса.

Общая часть:

const int P = 239017; // Если брать простой модуль, здесь стоит писать rand()!
// s - строка, n - её длина

Первый способ (я пишу так):

// deg[] = {1, P, P^2, P^3, ...}
// h[] = {0, s[0], s[0]*P + s[1], s[0]*P^2 + s[1]*P + s[2], ...}
unsigned long long h[n + 1], deg[n + 1];
h[0] = 0, deg[0] = 1;
for (int i = 0; i < n; i++) {
  h[i + 1] = h[i] * P + s[i];
  deg[i + 1] = deg[i] * P;
}
auto get_hash = [&]( int l, int r ) { // [l..r]
  return h[r + 1] - h[l] * deg[r - l + 1];
};

Второй способ:

// deg[] = {1, P, P^2, P^3, ...}
// h[] = {s[0], s[0] + s[1]*P, s[0] + s[1]*P + s[2]*P^2, ...}
unsigned long long h[n], deg[n];
h[0] = s[0], deg[0] = 1;
for (int i = 1; i < n; i++) {
  deg[i] = deg[i - 1] * P;
  h[i] = h[i - 1] + s[i] * deg[i];
}
auto get_hash = [&]( int l, int r ) { // [l..r]
  if (l == 0)
    return h[r];
  return h[r] - h[l - 1];
};

Отличия здесь два

Направление s₀P^n - 1 + s₁P^n - 2 + ... + s_n - 1 или s₀ + s₁P + s₂P² + ... + s_n - 1P^n - 1?

В первом способе, чтобы сравнить две строки [l1..r1] и [l2..r2], достаточно написать get_hash(l1, r1) == get_hash(l2, r2). То есть, функция get_hash честно возвращает хеш. Можно, например, найти количество различных подстрок, положив все хеши в хеш-таблицу.

Во втором случае функция get_hash на самом деле возвращает не хеш, а хеш, домноженный на некоторую степень P, поэтому придётся писать так deg[r2] * get_hash(l1, r1) == deg[r1] * get_hash(l2, r2) (на e-maxx правда чуть страшнее). А использовать хеши иначе не получится. Можно модифицировать функцию get_hash, использовать честный хеш true_hash(l, r) = deg[n - r - 1] * get_hash(l, r), но у такого способа есть минус — мы предполагаем, что знаем максимальную длину строки. Это не всегда удобно, а при онлайн-решениях иногда и не правда.

У второго способа ещё есть вариация с делением по модулю. Так писать точно не нужно.

С чего начинать массив h? С 0 или с s[0]?

Если мы начинаем с 0, мы получаем более короткий и быстрый код (да, да, чтобы if-у выполниться, нужно время!). Оценивая скорость, заметьте, что умножений будет столько же.

Если же мы начинаем в s[0], то получаем массив длины n, то есть экономим O(1) памяти.

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

Выбор простого модуля

Отдельный привет всем, кто говорит "число P можно выбирать любым". P должно быть больше размера алфавита. Если это так, то хеш, вычисленный без взятия по модулю, как длинное число, инъективен. Иначе уже на этапе вычисления без модуля могут быть коллизии. Примеры, как нельзя делать: алфавит "a..z", P = 13, алфавит ASCII 33..127, P = 31.

P.S. Кстати, как правильно пишется "хеш", или "хэш"? Моя версия — "хеш".

UPD: Подсказывают, что, если писать без unsigned, получится Undefined Behaviour. Спасибо Лёше Левину.

UPD: Чтобы хеш точно нельзя было сломать, можно точку P выбирать как max(Σ, rand()). Версия full пропатчилась. Спасибо Kaban-5, nk.karpov.

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

Алгоритм Куна ищет паросочетание в двудольном графе за O(VE). Реализация, данная на emaxx, укладывается в такой шаблон:

forn(i, n) {
  fill(used, 0);
  dfs(i);
}

Я обычно пишу так:

fill(used, 0);
forn(i, n) 
  if (dfs(i))
    fill(used, 0);

То есть, обнуляю пометки только если нашёл дополняющую цепь. Теперь Кун работает за O(|M|·E), где |M| — размер максимального паросочетания.

Решение можно ускорить ещё как минимум в 2 раза, используя жадную инициализацию паросочетания. Идея: применяем Куна не к пустому паросочетанию, а к паросочетанию размера хотя бы |M| / 2. Кстати, |M| / 2 — оценка снизу, если перед жадной инициализацией сделать random_shuffle, жадность найдёт паросочетание чуть побольше, и Кун будет работать чуть быстрее.

Новое для меня

Оказалось, можно заставить Куна работать ещё в несколько раз быстрее...

fill(pair, -1);
for (int run = 1; run; ) {
  run = 0, fill(used, 0);
  forn(i, n)
    if (pair[i] == -1 && dfs(i))
      run = 1;
}

То есть, теперь я не обнуляю пометки даже если нашёл дополняющую цепь.

Я успел потестить на нескольких задачах, например, на задаче про доминошки. Эффект: новая идея без жадной инициализации в 3 раза быстрее старой идеи с жадной инициализацией. Можно скачать тесты и решения и поиграться самостоятельно. Думаете, в доминошках специфический граф? Потестил на произвольном двудольном графе, эффект "на макс тесте в 10 раз быстрее".

Мне эта модификация Куна чем-то напоминает Хопкрофта-Карпа, т.к. получается, что мы за O(E) находим не один путь, а несколько. Непонятно, что стало с асимптотикой алгоритма. Может быть, она тоже улучшилась?)

Спасибо за внимание.

Если коротко: ребята, скажите, где можно студентам "почитать про сканирующая прямую"?

Мне интересны не решения геометрических задач по типу "найти два пересекающихся отрезка на плоскости" (которые как раз даже в wiki разобраны), а применение сканирующей прямой к структурам данных. Например, пусть на плоскости даны прямоугольники со сторонами параллельными осям координат и точки, нужно посчитать для каждого прямоугольника, сколько точек внутри? Самое простое решение за -- сканирующая прямая с деревом Фенвика.

Добрый день!

Скорее всего Вы когда-либо слышали про AVL дерево. Помните, там есть большие вращения и маленькие? Большое, конечно, можно делать как два маленьких, просто оно называется большим.

Вопрос: а есть ли тест, на котором дерево, построенное без использования больших вращений, имеет высоту хотя бы на 3 большую, чем правильное AVL дерево? А если нет теста, может, можно доказать корректность такого недо-AVL? =)

Вот код на C++, в котором
функция void add( node* &t, int x ); делает правильное добавление в AVL-дерево, а
функция void add_slow( node* &t, int x ); при нарушении инварианта всегда делает малое вращение.

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

UPD: У кого-то были проблемы скачать/прочитать код, поэтому not pastebin, short version

Добрый день.

Computer Science Center (совместная инициатива Школы анализа данных Яндекса, JetBrains и Computer Science клуба) продолжает регистрацию на массовые открытые онлайн-курсы по основам программирования. С 15 сентября 2014 года можно будет пройти три курса:

1. Алгоритмы и структуры данных (А.С. Куликов)

2. Программирование на языке C++ (А.В. Смаль)

3. Введение в архитектуру ЭВМ. Элементы операционных систем (К.В. Кринкин)

Данные три курса являются «джентльменским набором» начинающего программиста, преподаются на русском языке и бесплатны для всех желающих. Записаться на курсы можно на сайте CS центра. Для освоения курсов слушателям достаточно владеть школьной программой по математике, информатике, физике.

Для создания и размещения онлайн-курсов СS Center использовал образовательный плеер Stepic.

Более подробно про онлайн-курсы можно посмотреть на habrahabr.

Доброго времени суток.

Сейчас на сборах школьников к межнару нам регулярно приходится делать задачи... естественным образом мы некоторое время потратили на изучение testlib.h, плодами которого я и хочу поделиться =)

Такое ощущение, что текущий testlib.0.9.7 (revision 106)

1. Не компилируется под Windows g++ 4.8.1 с -std=c++03 и -std=c++11 (но компилируется с -std=gnu++03 и -std=gnu++11, т.е. с гнусными расширениями стандарта)

2. Никак не компилируется под MacOS g++ (или таки есть правильный набор ключей?)

И то, и другое лечится выпиливанием некоторых "не нужных" кусков testlib.h. Подскажите, пожалуйста, это уже где-нибудь обсуждалось? Что планируется с этим делать?

Есть еще 3: check.exe input correct-output file-not-found выдает вердикт wrong answer. Это бага или фича? =)

P.S. Совет "делайте в полигоне" не принимается, как минимум, у нас часто другой формат задач.

Коротко:

Речь пойдет в основном про Heavy-Light decomposition (далее HLD).

Мне интересно, существует ли реализации HLD, допускающие change-запросы и работающие в среднем за на get-запрос. Если да, пожалуйста, ссылку в студию. Если нет, докажите (опровергните), пожалуйста, идею кэширования (ниже подробно описана).

Подробно

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

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

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

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

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.me/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.me/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/Sk1/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 контесты с обоих серверов, да еще и только те, куда точно можно войти, используя логин-пароль с кубка.