Сайт соревнования. Нужно иметь логин (получать у координатора сектора).

Превратили бомбермен в какое то говно, извиняюсь

out.printLine(L * M / N);

Алгоритмический подход к решению: переформулируем задачу, пусть первый выбрал какие-то l чисел, а второй пытается эти числа угадать за m попыток. Без ограничения общности, будем считать что первый ткнул в числа 1..l; тогда вероятность того что второй угадает ровно k чисел p(k) = C(k, l)*C(m — k, n — l)/C(m, n). Тогда нужно найти такое k, что сумма на префиксе будет примерно 0.5 . Выпишем формулу как пересчитывать ответ для k через k-1 (распишем цешки и получим дробь, на которую нужно умножить при переходе). Чтобы не было проблем с точностью, считаем не p(k) а log(p(k)) (операции у нас только умножить/разделить, которые легко заменяются на плюс/минус). Ну а дальше считаем сумму на префиксе и проверяем что она больше 0.5:)

Ну, можно её решить и без интуитивных соображений. То, что точно решать не надо (т. е. ответ может отличаться на 10) намекает на то, что можно добиться успеха простой симуляцией. Мы можем посчитать для фиксированного K какова вероятность его получить: . Идём себе по k и жадно прибавляем эту величину, пока она не превзойдёт 0.5, не забываем, что чтобы ничего не переполнилось, числитель и знаменатель вычислять явно не надо, например, можно посчитать дробь в логарифмах и взять экспоненту.

И знать никаких соображений про биномиальное распределение не надо.

UPD: ой-ой-ой, я не увидел коммента JKeeJ1e30, который рассказывает ровно то же самое.

Естественно на плюсах? :)

у нас O(Q * N²), мы считали sum[i][j] — количество путей из i в j по модулю 10⁹ + 7, и если эта величина равнялась нулю, то считали, что ребра между i и j нет

Вроде не должно было.

У жюри было два AC решения: QN³/32 (понятно, как) и QN² (ровно то, что описал Kostroma)

Вышли, пожалуйста, код на [email protected].

У нас первая команда сдала O(QN³) с битовыми масками. Они смогли это сделать в основном потому, что свято верили, что у них работает за O(QN²). После конца тура их конечно быстро разочаровали...

400^3 * 800 = 10^11 — нормально:)

Я не Петр, но отвечу)

Мы запихали следующее:

1)Делаем понятно что за 2^26*26 (сначала сгенерируем все проигрышные позиции-надмаски масок букв в словах, потом пройдем с конца к началу по массиву масок и проверим для всех позиций какими они являются).

2)scanf — это очень плохо, используем gets()

3)Буквам сделаем random_shuffle.

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

5)Основную динамику можно делать "вперед", а можно "назад". Один из этих способов у нас получил TL65, второй AC.

За счёт битовых операций можно с 2^26*26 ускорить до 2^22*22+2^26*4. Это все ещё небольшой TL — зашло после убирания ifов во внутренних циклах.

Авторское решение работает за 2²⁶·26 / 32. То, что сдали две команды, насколько я могу понять — это нечто среднее между медленным решением за 2²⁶·26 и быстрым.

Отметим подмножества, заданные словами. Придумаем медленную динамику в два этапа.

(1) Для каждого подмножества букв снизу вверх, если оно запрещённое, распространим это на все его ближайшие надмножества:

for (int s = 0; s < POW_2_26; s++)
  if (f[s])
    for (int j = 0; j < 26; j++)
      if (!(s & (1 << j)))
        f[s ^ (1 << j)] = true;

Заметим теперь, что запрещённые подмножества можно считать выигрышными для тех, чья очередь хода при нахождении в них.

(2) Для каждого подмножества букв сверху вниз, если оно проигрышное, сделаем выигрышными все его ближайшие подмножества:

for (int s = POW_2_26 - 1; s >= 0; s--)
  if (!f[s])
    for (int j = 0; j < 26; j++)
      if (s & (1 << j))
        f[s ^ (1 << j)] = true;

Это решение использует булевский массив f и работает несколько секунд — слишком медленно. Предлагаемая оптимизация — векторизовать битовые операции так, чтобы за одну операцию с int32 выполнялось 32 нужные нам операции с булевским массивом, упакованным в битовый массив. Теперь вместо элемента массива f[s] мы будем пользоваться битом g[s >> 5] & (1 << (s & 31)).

Для переходов по j >= 5 наша динамика отлично подходит, например, из первой части получается следующее:

for (int t = 0; t < POW_2_21; t++)
{
  <...>
  for (int k = 0; k < 21; k++)
    if (!(t & (1 << k)))
      g[t ^ (1 << k)] |= g[t];
}

Такой код за одну операцию действует одновременно на вектор из 32 битов. Например, если t = 0 и k = 0, действие g[t ^ (1 << k)] |= g[t]; (то есть g[1] |= g[0]) эквивалентно следующим 32 действиям медленной версии:

f[32] |= f[ 0];
f[33] |= f[ 1];
f[32] |= f[ 2];
...
f[62] |= f[30];
f[63] |= f[31];

А вот вместо троеточия <...> нужно сделать переходы, которые раньше происходили при j < 5. Это менее тривиально. В первой динамике это можно сделать за диапазона, то есть за 5·C действий, так:

g[t] |= (g[t] & 0b_0101_0101_0101_0101_0101_0101_0101_0101) <<  1;
g[t] |= (g[t] & 0b_0011_0011_0011_0011_0011_0011_0011_0011) <<  2;
g[t] |= (g[t] & 0b_0000_1111_0000_1111_0000_1111_0000_1111) <<  4;
g[t] |= (g[t] & 0b_0000_0000_1111_1111_0000_0000_1111_1111) <<  8;
g[t] |= (g[t] & 0b_0000_0000_0000_0000_1111_1111_1111_1111) << 16;

Здесь 0bXXXX — двоичные константы. Например, второе действие выполняет следующие 16 эквивалентных действий с булевским массивом:

f[t +  2] |= f[t +  0];
f[t +  3] |= f[t +  1];
f[t +  6] |= f[t +  4];
f[t +  7] |= f[t +  5];
...
f[t + 30] |= f[t + 28];
f[t + 31] |= f[t + 29];

Но, во-первых, это не очень быстро, а во-вторых, вторая динамика сложнее, и такой подход будет ещё более трудоёмким. Так что для троеточия <...> будем использовать другую идею. Заметим, что наша динамика монотонна: в первой динамике f[s] влияет только на f с индексами > s, а во второй — только на f с индексами < s. Придумаем троеточие <...> для второй динамики, а для первой получится аналогично.

Итак, что происходит внутри одного g[t] во второй динамике? Сначала верхний бит (с номером 31) как-то влияет на биты 30, 29, 27, 23 и 15. Затем следующий сверху бит (с номером 30) как-то влияет на биты 28, 26, 22 и 14. Далее следующий бит (с номером 29) как-то влияет на биты 28, 25, 21 и 13, и так далее. Ещё очень важно, что единственный способ влияния — операция ИЛИ, то есть единички могут только появляться.

Разобъём g[t] на верхний и нижний куски по 16 битов. Тогда происходящее внутри g[t] можно разбить по времени на два отрезка:

(1) верхние 16 битов влияют на значение g[t] (на все 32 бита),

(2) нижние 16 битов влияют на значение g[t] (фактически только на нижние 16 битов).

Для каждых возможных верхних 16 битов предподсчитаем, как они повлияют на значение всех 32 битов — фактически получится маска из 32 битов, которую нужно по-OR-ить с g[t]. Запомним эти маски в массиве hi [1 << 16].

Затем для каждых возможных нижних 16 битов предподсчитаем, как они повлияют сами на себя — получится ещё одна маска. Запомним её в массиве lo [1 << 16].

Теперь, если у нас есть g[t] до применения к нему динамики, то мы можем быстро узнать, каким он станет после применения к нему динамики. А именно, пусть g[t] = (x << 16) + y, где 0 <= x, y < (1 << 16). Преобразования будут таковы:

g[t] |= hi[x];
g[t] |= lo[y];

Конечно, значение y нужно вычислить уже после выполнения первой строчки, так как оно могло измениться.

Итак, мы научились всего за два действия применять преобразования второй динамики к 32-битному элементу массива g[t]. Итоговая версия второй динамики после предподсчёта такая:

for (int t = POW_2_21 - 1; t >= 0; t--)
{
  g[t] |= hi[g[t] >> 16];
  g[t] |= lo[g[t] & 0b_1111_1111_1111_1111];
  for (int k = 0; k < 21; k++)
    if (!(t & (1 << k)))
      g[t ^ (1 << k)] |= g[t];
}

Для первой динамики нужно, наоборот, сначала влиять нижними битами на нижние и верхние, а потом верхними на самих себя. Сам предподсчёт каждого из массивов lo и hi можно сделать медленной динамикой за 2¹⁶·32.

Вот полный пример кода, реализующего эту идею. Авторские решения работают за 0.5 (C++), 0.7 (D) и 0.9 (Java) секунды на проверяющих серверах. Ограничения по времени выставлены не очень жёстко (2 для всех языков и 3 для Java), что (учитывая ещё не очень умно сделанные тесты) позволяет пройти достаточно оптимизированным промежуточным решениям.

Нет, не было =)

На самом деле, более правильный ответ на клар таков: k ≥ 3.

А, чёрт, а я оптимайзил сидел H :(

Перейдем к системе счисления с основанием 1001. Тогда если мы взяли a[1] платиновых медалей, a[2] золотых и т.д., то представим это в виде a[1] * 1001^9 + a[2] * 1001^8 + ... + a[10]. Эту величину нужно максимизировать. Если человек i идет на дисциплину j и приносит медаль достоинства k, то стоимость ребра из i в j 1001^(10 — k). Теперь просто нужно найти паросочетание максимального веса. Решаем минкостом.

G = mincost flow.

Вес ребра — вектор длины "количество медалек". Для ускорения можно веса сжать в два 64-битных числа.

Заходили и ford-bellman и dijkstra.

Подробнее рассказывать?

Получить задачи до старта контеста?

В смысле?

Решается так: зафиксировали один вектор, вычли его из остальных, как в Гауссе, после этого оставшиеся вектора нужно разбить на классы колинеарных, для этого приведем их к инвариантному виду (поделим на первую не нулевую координату) и отсортируем.

У нас зашел пропих хэшей правильно ориентированных единичных перпендикуляров к одному из двух векторов плоскости, где перпендикуляр также лежит в плоскости. Хэш считался просто как полином от координат вектора, домноженных на степень десятки и округленных. Вычисления в double упорно давали WA52, после использования long double прошло.

Мы придумали вот так характеризовать плоскость: зафиксируем две случайные точки в d-мерном пространстве, и найдём на каждой плоскости ближайшую точку к каждой из них. Ближайшая находится как минимум квадратичной функции по двум переменным, через решение системы двух линейных уравнений (производные приравниваем нулю).

у меня...

Как она вообще решается?

Ага, вышло примерно так же. Осталась только наша команда и координатор, который ютуб смотрел :)

Олег кажется уронил http://acm.math.spbu.ru:8087

От туда скорее всего уже все уехали, и с учетом того, что он сам не поднялся, видимо до завтра не будет. Результаты чемпа вот http://acm.math.spbu.ru/cgi-bin/monitor.pl/m131006.dat Думаю скоро разморозят. У нас 10, у банановых 9, что еще интересного я не знаю. Штраф минут на 40 хуже, чем у вас. Надо было все с плюса сдавать.

Пока что на Contest писали несколько команд ИТМО и США. Мы будем постепенно приглашать больше команд участвовать на Яндекс.Contest.

Дорешку открыли

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