Добрый день! от футболок решили отказаться в основном по двум причинам: во-первых, из-за больших сложностей с отправкой и доставкой футболок почтой и отсутствия возможности как-либо влиять на сроки и качество доставки, а так же негатив участников, возникающий из-за несвоевременного получения посылки. Наверняка здесь есть много участников RCC прошлого года, чья футболка так затерялась в недрах почты или по независящим от нас причинам была возвращена... Во-вторых, мы регулярно получаем просьбы и комментарии участников о желании получать сертификаты, подтверждающие участие или квалификацию.

да, почта майл.ру работает надежнее почты России!

Те, кому удача в субботу не улыбнется, а также те, кто по тем или иным причинам не смогут принять участие в раунде, смогут попробовать свои силы во втором отборочном раунде 25 апреля в 12:00, а при необходимости и в третьем – 31 мая в 13:00.

когда Russian Code Cup проводит контест вечером в субботу, в мире расстраивается один knst

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

Была, WA на втором тесте в первой задаче, тот же код в GCC зашёл

Так вот почему у меня неправильно работает!! Спасибо =)

У меня зашла корневая.

Так разрешён же prewritten code. Чего там писать, если есть template/generic класс дерева интервалов и класс матрицы?

Я криворук, но у меня и ДО получило TL 2.

[ignore previous message]

А * у тебя — произведение чисел в системе счисления по основанию 10 или произведение полиномов?

Я думал примерно так: заменим числа x, y, z в равенстве полиномами с неизвестной базой w и коэффициентами, равными их цифрам. Раскроем скобки и перенесем неизвестные в одну сторону. Получим полином от w, который будет равен нулю при любом w тогда и только тогда, когда все его коэффициенты будут равны нулю. Что и означает x·y = z

А что не так с этими посылками: http://mirror.codeforces.com/gym/100653/submission/10504555 и http://mirror.codeforces.com/gym/100653/submission/10504510 ? На RCC этот код зашёл.

Храним для всех возможных 0<=x<m ответ. Переход n->(n+1) это тупая динамика, а n->(2*n) это уже FFT по тому самому модулю. К счастью, модуль хороший: MOD-1 делится на 2^23. FFT с комплексными не заходит по точности.

Я решал через ДП по состоянию: 1. Кол-во пар, которые надо рассадить 2. Кол-во одиночных математиков, которые надо рассадить 3. Кол-во одиночных философов, которые надо рассадить 4. Кто был посажен последним (математик или филосов) 5. Кто был посажен предпоследним (математик или филосов) 6. Есть ли у посаженного последним напарник среди еще не рассаженных

Пересчитывать за O(1) думаю понятно как

Можно такой динамикой:

dp[n1][n2][pairs][last][last_paired] — сколько способов расставить числа на первых n1+n2 местах, чтобы среди них было pairs пар одинаковых чисел, чтобы маска типов последних двух чуваков была last ( ≤  3), и что у последнего (была пара)/(не было пары). И математиков n1 и философов n2.

Переход -- перебрать, кого из 2-х ставим, будем ли использовать число, которое уже было или не будем. Когда-то вычесть 1 случай, когда текущий равен последнему.

ДП ([номер позиции на которую надо поставить очередного М или Ф], [число непосаженных математиков у которых парного им философа уже посадили], [число непосаженных философов у которых парного им математика уже посадили], [кто предыдущий-М или Ф], [кто пред-предыдущий-М или Ф], [поставлен ли предыдущим М или Ф из тех, чья пара уже выставлена]). итого 16 млн состояний при N=100 и переходы между ними что-то около O(1).

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

Как сюда прикрутить изменения? Сделаем дерево отрезков (да и корневая, как выше подтвердил Zhukov_Dmitry, тоже заходит, потом перепишу свою аккуратней:) для корневой можно посчитать ответы внутри каждого блока той же наивной динамикой), которое будет для каждого отрезка знать, сколько есть способов валидно нарезать этот отрезок без 0/1/2 символов слева/справа. При изменении нужно будет проапдейтить только логарифм отрезков. Как сливать такие отрезки? У отрезка-объединения слева будет столько свободных символов, сколько было свободных символов на префиксе у левого отрезка, справа — столько, сколько было свободных на суффиксе у правого; нужно перебрать, что происходит на стыке левого и правого отрезка — либо они просто сложились, либо же код какого-то числа был разбит на части, и попал и в суффикс левого отрезка, и в префикс правого (т.е. объедиение свободных символов суффикса левого отрезка и префикса правого отрезка дало нам валидный код). Так как коды у нас короткие, то все такие разбиения можно перебрать.

А ответом будет число разбиений без свободных символов слева и справа для вершины-корня.

А что приходило? PE?

Ну по wa/pe на первом тесте можно было догадаться, что что-то здесь не так

(а еще можно тулзы использовать, которые сами на тестах проверят :) )

BigInteger... дааааа :)

for (int i = 0; i<yl; ++i)
{
        int kof = y[yl - 1 - i] - '0';
	for (int j = 0; j < xl; ++j)
	{
	     temp[i + j] += kof*(x[xl-1-j]-'0');
	}
}

Да, это нормально, к сожалению, хоть и не хорошо. Я для таких вещей пишу инкапсулятор для программы. Т.е. программу, которая загружает сборку другой программы из массива байт и вызывает в этой сборке функцию Main.