Нет, не TL)

Пошаффлим и пройдём с посорченным списком из 10 минимальных элементов. Сначала сравниваем с максимумом, если прокатывает — вставляем бинпоиском. Понятно, что почти всегда будет 1 сравнение на элемент (т.к. максимум из 10 минимальных обычно меньше рандомного элемента).

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

Ну там для рандомного порядка индексов надо просто искать k минимумов обычным методом вставок. Почему-то сразу верилось, что такое успеется за указанное ограничение. Как-то интуитивно опирался на то, что 700 намного больше корня из n.

P.S. Редкий случай, когда в div2 задачу сдали быстрее, чем в div1. Пойду возьму с полки пирожок.

Строим дерево отрезков за n-1. Потом за klogn узнаём минимумы.

Двоичную кучу можно за O(n) построить.

Есть другое решение: Ищем вначале 1, потом 2, ... всего 10 итераций поиска минимума. Все время храним для каждого числа список тех, которых оно оказалось больше в результате сравнения. На каждой итерации берем все числа, которые оказались больше только предыдущих минимумов и устраиваем между ними чемпионат на выбывание. Каждый чемпионат проходит за количество кандидатов-1 сравнений. На первой итерации будет n кандидатов. На каждой следующей логарифм, тк глубина дерева в чемпионате логарифмическая, а кандидатом может быть только тот, кто проиграл лишь предыдущему минимуму

В А две динамики:

D1[k][mask] = наименьшая пара чисел (количество шагов; занятое место на последнем шаге) необходимые для того, чтоб k-тый грузовик вывез все предметы помеченные в битовой маске mask. Пересчитывается перебором последнего предмета, помещенного в грузовик.

D2[k][mask] — наименьшее количество шагов необходимых для того, чтоб первые k грузовиков вывезли все предметы помеченные в битовой маске mask. Пересчитывается перебором всех подмасок соответствующих грузу, перевезённому последним грузовиком.

Плюс восстановление ответа.

А: Найдём ответ для каждого подмножества предметов и для каждого контейнера динамикой по битмаскам (dp[i][bit]). А потом рекурсией с отсечением по ответу переберём контейнер для каждого предмета. Жутковатый код: http://pastebin.com/5VUN0Vds

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

Общая схема решения:

1. Рассмотрим точки в случайном порядке.

2. Будем наращивать ответ. Если очередная точка уже лежит в ответе, то переходим к следующей, в противном случае говорим, что она обязательно должна входить в новый ответ. Вероятность этого события 3 / i.

3. После фиксации одной точки, идём сначала и ищем две новые точки для ответа таким же способом. На этот раз вероятность ошибки 2 / i.

4. Для двух фиксированных точек опять идём сначала и подбираем третью. Итоговая сложность — O(n), так как матожидание сложности каждого шага константное.

По трём точкам искать подходящую окружность уже скорее техническая задача: строим прямые или окружности Аполлония и пересекаем.

Пусть N = max(10, H, W), H, W — максимальные ширина и высота куда мы зашли. Сделаем бфс с нашей клетки до клетки (N, N), но можем использовать квадрат N + 1xN + 1 с учетом найденных стен. N + 1 берем для того, чтоб нормально увеличивать N и до клетки (N, N) всегда можно было дойти.

Не знаю, правильное ли, но зашедшее решение(в дорешку):

Считаем, что там где еще стен не видели — стен нет. Поддерживаем maxn — максимум встретившейся координаты. Если мы в клетке maxn, maxn, то ++maxn Делаем bfs из клетки (maxn, maxn). Пытаемся перейти из текущей вершины в ее предка в bfs'е (т.е пойти по кратчайшему пути)

В Div2 (за n² + 1000 шагов) можно было просто устроить обход вдоль стенки. Он на 200 × 200 занимает 2500-3000 шагов без оптимизаций и ~2000, если немного улучшить.

В Div1 (за 5n + 300 шагов) для 200 × 200 надо было уложиться в 1300 шагов, поэтому такое решение уже не должно было пройти. Тут помогает заметить, что лабиринт квадратный, а значит, нам надо идти примерно вдоль главной диагонали. Будем запоминать, где мы уже видели стены, и искать следующую не посещённую клетку, в которую хочется пойти, каким-нибудь поиском в ширину (я просто на каждом шаге заново просматриваю 100 клеток, достигнутых поиском в ширину из текущей; а можно запускать новый поиск, только когда мы пришли к промежуточной цели или уткнулись в стену). В клетки ближе к главной диагонали и дальше от начала координат больше хочется пойти. У меня весовая функция клетки — это row + col - abs (row - col). Такое решение обычно проходит лабиринт 200 × 200 за 800-1100 шагов.

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

Кстати, об альтернативном пути для дорешивания этой задачи: ничто в условии (а также в интеракторе) не запрещает пойти через лес.

Обозначим за x вес на ребре после добавления потенциалов. В каждой компоненте связности (слабой) поставим 0 в одну из вершин. Далее идем по ребру в любом направлении и однозначно восстанавливаем во всех вершинах значения в виде (Ax+b), иногда попутно получая равенства ax+b=cx+d, из которых находим x. Если получили несколько таких значений x(или не разрешимое уравнение) — все плохо. Если ни одного — тогда можно взять x = 0 (или любому другому числу)

Сейчас я вижу в системе четыре ваши посылки, и у всех на восьмом тесте ответ -1 — как и у жюри. А на девятом, действительно, WA, причём разные (один раз -1, три раза не -1).

Это --ц, господа.

На yandex или где?

Не слишком удивелен если честно. Там интерактивы работают никак. Призывается lperovskaya. В ejudge и на онсайте работало нормально.

Контест начался на яндексе раньше из-за проблем с ejudge я так понимаю. Почему не отложили синхронно — не знаю. По поводу задачи C — это бага дорешки или на контесте тоже был кривой чекер? Будет ли rejudge?

Первые степени простых не влияют. Поэтому можно искать только простые делители до 10^6. То, что осталось достаточно провеирть на квадрат, если не квадрат, то можно считать одним большим простым числом.

Прелположим, что все правила в грамматике имели бы в правой части не более одного нетерминала. Тогда для правила A —  > Baa..abb..b проведем ребро из A в B веса, равного разности количества букв "b" и букв "a" в правой части, а для правила A —  > aa..abb..b проведем ребро из A в специальную вершину-сток T с понятным весом. Получилась задача о поиске кратчайшего пути из стартового нетерминала S в T с отрицательными весами. На помощь приходит алгоритм Форда-Беллмана.

Теперь обобщим. Для каждого нетерминала X будем считать его "расстояние" — минимальную разность числа букв "b" и "a" среди конечных слов, выводимых из нетерминала X. Инициализация простая: если из нетерминала X выводится какая-то строка только из терминалов, то это и будет начальное "расстояние". Теперь будем n раз делать релаксацию: будем бежать по всем правилам и если оказалось, что во-первых, для всех нетерминалов в правой части правила уже посчитаны какие-то "расстояния" (то есть можно вывести хоть какое-то конечное слово), а во-вторых, суммарные "расстояния" в правой части плюс разность числа букв "b" числа букв "a" в правой части меньше, чем текущее "расстояние", то обновляем "расстояние" до нетерминала в левой части.

В конце проверяем, есть ли отрицательный цикл, и достижим ли он из стартового нетерминала. Сами расстояния храним в длинном числе.

Вопрос в том, сколько же итераций нужно сделать "Форду-Беллману". Точно не больше n + m, и есть идея (подтвержденная на контесте Accepted-ом), почему n: предположим, что ответ конечен. Построим вспомогательный граф, в котором проведем ребро между нетерминалами X и Y, если мы в какой-то момент при выводе оптимального ответа воспользовались правилом, где X в левой части, а Y — в правой. Может быть, используя этот ацикличный граф, можно доказать, что итераций надо n.