Задача A: Ответ равен floor(N*M*0.5). Поскольку на доске N*M клеток, и каждая доминошка покрывает ровно 2 клетки, то больше положить точно нельзя. Теперь покажем, как положить ровно столько доминошек. Если N чётно, то кладём M рядов по N/2 доминошек и занимаем всю доску. Если N нечётно, то укладываем полностью (N-1) ряд доски как написано выше, а последний ряд забиваем floor(M/2) доминошками. При этом максимум останется одна незанятая клетка, в случае если N и M нечётны.

Задача B: Разумеется нужно было написать неквадратичное решение. Проходим по заданной строке и считаем, сколько раз встречается каждый символ. Пусть K_i - количество вхождений символа с ASCII-кодом i в строку S. Тогда ответ равен sum(K_i²). В коде решения часто возникали проблемы:

1. Писали квадратичное решение (двойной цикл по строке).
2. Забывали поставить int64. Либо в ответе, либо в возведении K_i в квадрат.
3. Неверное выводили int64.

Все эти проблемы хакались тестом из 100000 одинаковых символов. Из-за этого процесс хакания превратился в игру "кто быстрей захакает очередное решение B", поскольку новички часто допускали все эти ошибки. Эта проблема ещё усилилась из-за того, что GCC-компилятор на сервере оказывается является MinGW-компилятором, поэтому на нём не работает вывод printf("%lld", ...). Ещё одна странная проблема, возникшая у хакеров - молчаливое обрезание теста по длине около 30000 при копировании его в редактор. Естественно, переполнение в решении из-за этого исчезало.

Задача C: В задаче требовалось, чтобы все коровы находились строго внутри маршрута. Изначально я планировал сделать нестрого, но тогда ответ для случая одной коровы оказался бы странным=) На самом деле разница в решении невелика. Ответ для "строгой" задачи всегда на 4 больше, чем для "нестрогой". Некоторые участники предпочли добавить к каждой точке четырёх её соседей  крестиком, чтобы перейти к нестрогой задаче.

Нестрогая задача решается следующим образом. Заметим, что искомый маршрут всегда можно представить восьмиугольником, возможно с нулевыми сторонами. Нужно было взять четыре пары параллельных прямых и "прижать" их к точкам. Иначе говоря, мы находим для набора точек ограничивающий прямоугольник, параллельный осям координат. Затем находим ограничивающий прямоугольник для набора точек на повёрнутой на 45 градусов картинке. Теперь пересекаем эти два прямоуольника (как заполненные фигуры). Получаем в общем случае восьмиугольник, который является искомым. Для реализации нужно посчитать минимумы и максимумы X, Y, X+Y, X-Y по всем точкам, потом посчитать по ним ответ по нетривиальным формулам.

Многие участники решили задачу по-другому. Легко понять, что для перемещения на вектор (X, Y) пастуху требуется max(|X|, |Y|) ходов. Так вот, можно заставить пастуха ходить по вершинам выпуклой оболочки. Нужно запустить стандартный алгоритм Грэхема, потом обойти вершины на оболочке и просуммировать max(|X'-X|, |Y'-Y|) для соседних вершин в ней. Это решение также правильное.

Была идея сделать ограничение координат по модулю до 10⁹, но потом решили, что незачем лишний раз требовать int64. Возможно лучше бы int64 было в этой задаче, а не в задаче B.

Задача D: Условие задачи выглядит запутанно и воинственно. Дело в том, что легенда была навеяна занятиями по гражданской обороне в университете. Это такой предмет, на котором в частности учат, что делать до и после ядерного взрыва...

Сперва нужно заметить, что чем больше боеголовка, тем больше вероятность выполнить задание. Это вполне разумно с житейской точки зрения. Функция P(D, R) возрастает по R при фискированном D. Очевидно, что при этом и вероятность повредить как минимум K объектов тоже возрастает по R. Следовательно, можно было найти искомый радиус бинарным поиском. Для того, чтобы это сделать, нам нужно научиться находить вероятность выполнить задачу при фиксированном и известном радиусе R.

Теперь нужно решить такую задачу: есть N объектов, каждый из которых разрушается с заданной вероятностью (p_i). Нужно найти вероятность разрушения как минимум K из них. Задача решается динамическим программированием, очень похожим на подсчёт биномиальных коэффициентов по треугольнику Паскаля. Пусть R[i, j] - вероятность поразить ровно j объектов среди первых i из всех заданных. Если мы посчитаем все значения R для 0<=j<=i<=N, то ответ можно будет вычислить как sum_{j=k..N} R[N, j]. Начальное условие динамики: R[0, 0] = 1. Пересчёт выполняем по формуле R[i, j] = R[i-1, j-1] * p_i + R[i-1, j] * (1-p_i), считая, что все элементы R с j<0 или j>i нулевые.

Экспериментально было выяснено, что многим кодерам (мне в том числе) в голову первым делом приходит идея учитывать только K ближайших к эпицентру строений. То есть считать, что вероятность выполнить задачу равна просто p₁ * p₂ *... * p_K. Это неверно: например, если есть два строения на одинаковом расстоянии, то вероятность поразить хотя бы одно из них равна 1-(1-p)² вместо p. Но я решил сделать тем, кто так посчитал, приятное и включил в претесты только такие случаи, когда это решение работает=) Так что это неверное решение специально проходило все претесты.

Задача E: Пусть D = b²-c   - четверть дискриминанта уравнения. Решения уравнения равны -b-sqrt(D) и -b+sqrt(D). Таким образом, есть два типа корней: иррациональные корни вида x +- sqrt(y) и целые корни. Будем считать количество корней отдельно для двух типов.

Иррациональные корни имеют вид x+sqrt(y) (y - не точный квадрат). Утверждается, что если два числа такого вида равны, то их x и y совпадают. Это можно легко проверить на бумажке, главное принять во внимание, что sqrt(y) иррационально. Таким образом, если два иррациональных корня равны, то и уравнения совпадают. Следовательно все иррациональные корни всех уравнений различны. Будем перебирать b=1..N. Для каждого из них нужно найти количество уравнений с положительным дискриминантом, не являющимся точным квадратом. То есть количество c=1...M таких, что D = b²-c - не точный квадрат. Можно определить отрезок [L; R], значения которого принимает D (L >= 0). Потом взять его длину (R-L+1) и вычесть количество точных квадратов в нём. Это и будет количество уравнений с иррациональными корнями для фиксированного b. Умножаем это число на два (корня два) и прибавляем к ответу.

Теперь разберёмся с целыми корнями. Для фиксированного b мы определили отрезок [L;R] для D. Тогда sqrt(D) будет принимать целые значения  [l; r] = [ceil(sqrt(L)); floor(sqrt(R))]. Подставляем это множество значений в формулу для корня и получаем, что целые корни всех уравнений с фиксированным b составляют отрезки [-b-r;-b-l] и [-b+l;-b+r]. Однако целые корни существенно могут быть одинаковыми. Поэтому мы должны пометить в глобальной структуре данных, что все корни из этих двух отрезков "найдены". После того, как мы переберём все b=1..N, в этой структуре данных нужно найти количество чисел, помеченных хотя бы раз.

Такая структура данных реализуется на массиве. Все целые корни уравнений лежат в пределах от -10000000 до 0. Заводим массив Q чуть большего размера. Для того, чтобы отметить отрезок [s; t], мы увеличиваем на 1 элемент Q[s] и уменьшаем на 1 элемент Q[t+1]. В конце работы алгоритма пробегаем весь массив Q слева направо и считаем префиксные суммы в массив S. То есть S[i] = Q[-10000010] + Q[-10000009] + ... + Q[i-1] + Q[i]. Тогда S[i] будет означать то, сколько раз мы всего пометили число i. Теперь пробегаем массив S и считаем количество ненулевых элементов - это и есть количество различных целых корней.

Решение работает за O(N), поскольку требуется перебирать все значения b. Очень вероятно, что есть чисто комбинаторная (O(1)) формула для ответа=)

Итого. Я считаю, что в зачадах раунда были две проблемы. Первая - отсутствие технически сложной задачи. Из-за этого кодеры высокого уровня решили все задачи за первый час, и мучались с хаканием в нестабильной системе остальной час. Мне кажется, задача E в раунде должна быть действительно сложной для написания. Вторая проблема - огромное количество хаков по задаче B. Надо было всё-таки сделать длину строки до 40000. Ещё интересный вопрос: почему смешиваются дивизионы? Было бы разумнее, если каждая комната была либо полностью первым дивизионом, либо полностью вторым. Тогда кодеры первого дивизиона будут хакать решения сложных задач, а не ловить элементарные ошибки новичков.

Напоминаю, что в системе тестирования вы можете посмотреть тесты к задачам.