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

Кэп намекает, что замечание снизу не просто так. А даже, если и отсорчены, то по сложности по мнению авторов/администрации, а не вашему умению их решать

Все, кто в этом раунде не попали в 700, могут участвовать в wildcard.

Ну не автоматически же :) Нужно будет зарегистрироваться..

Спасибо, пост исправлен. В первом wildcard могут участвовать все, кто не вышел во второй раунд сразу.

Должно получаться зарегистрироваться вне конкурса. Даже если не прошел квалификацию.

Вы есть в списке зарегистрированных

Это просто не отображается, что ты зарегистрировался. Чтобы убедится, что все ок, найди себя в списке зарегистрированных.

I guess authors will not change statements 5 minute before the contest:)

Я думаю так, ибо иначе было бы не справедливо.

По логике должны быть отдельные комнаты для участников вне конкурса. Больше отдельных быть не должно.

Вроде так. Но только offic./unoffic. в разных комнатах.

Внеконкурсные отдельно от участников чампа. Остальные вроде как угодно

Скандалы-интриги-расследования! Перенесли на пять минут! Заговор фейсбука или досадная оплошность контакта? Мы раскроем эту тайну!

Будто никто и так не заметил.

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

I cannot submit. (unofficials) why?

У меня тоже такая проблема.

Подтверждаю :) upd: насторожило еще то, что при начале не появилась привычная табличка со ссылкой на задачи

Еще насторожило то, что до конца било написано красными 'зарегистрироваться', а должно било зеленым 'зарегистрирован'. Ой, не успел написать, опоздал)

I noticed that when I hit the register button, the front screen would still say that I was not registered, but when I went into the Friend Standings area, it displayed my name. (unofficial with the * by it)

EDIT: Did anyone else see this?

Даааа, разыграл нас КФ(

I'm sorry. Yes. It is just the result of wrong contest policy setup. It will not be such issue in the future. Sorry again.

Съешь ещё этих мягких французских булок да выпей чаю.

it seems to be unrated. the official notice mentioned this.

ты вводишь неупорядоченный массив

integer берёт 2^32 значений. Так как я понял, ты имеешь ввиду Delphi

Если брать 2-байтные знаковые числа, то ограничение сверху не 32676, а 32767

Поддерживаю вопрос. Как нужно было решать D? BFS, даже оптимизированный, получал TL 11

del

Я писал обычную ДП по дереву dp[i][j] сколько вершин в поддереве находится на расстоянии j от корня i. Дальше несложно посчитать и весь ответ.

Динамика dp[i][j] — сколько есть вершин в поддерве c корнем i и на расстоянии j от этого корня. Далее по ней легко считался ответ.

UPD: тьфу, не C, а D. Пардон.

Методом пристального смотрения на двоичные деревья. :-)

Я делал что — предположим, что максимальный символ в общей строке — k. Находил формулой минимальную и максимальную позицию такого символа в обоих отрезках, рассматривал три случая — берём в каждом из отрезков самый левый символ k, какой-то средний, или самый правый. Потом отходил от этого символа в обоих отрезках макимально налево, максимально направо и брал минимум по обоим отрезкам.

В общем, невнятное у меня решение, но корректное. Уверен, что есть решение чуть ли не в пару строк какой-нибудь мега-битовой формулой.

Решал ее за O(N * K * log(N)). Итоговый код отправить не успел, посмотрим, что будет в дорешке.

Я делал динамику. Обходим в глубину. Храним для каждой вершины число ее сыновей определенной глубины. И совмещаем вычисления с динамикой. Для каждой вершины прибавляем к ответу число пар, для которых эта вершина — LCA. Оно считается просто — просматривая сыновей, суммируем произведения количества вершин глубины p (относительно текущей) в каждом из поддеревьев на количество глубины k-p в всех ранее просмотренных поддеревьях. Ну и отдельно плюс число вершин глубины k — каждую из них можно соединить с нашим корнем.

down[v][k] = (сумма по u — сыновьям v)down[u][k — 1]

up[v][k] = up[p(v)][k — 1] + down[p(v)][k — 1] — down[v][k — 2]

up[v][k] — количество путей длины k с началом в v, у которых первое ребро вверх, down[v][k] — то же самое с первым ребром вниз.

Я решал как-то по суровому, но все-равно забыл про лонг лонг=) dp[i][l] — кол-во путей длинны l из вершины i, sum[i][2] — сумма уже просчитанных путей четной/нечетной длинны из вершины i. Тогда для всех j смежных с i, dp[i][l] = sum[j][(l-1)%2]-sum[j][l%2].

Да, прекрасно получалось.

Я вроде упихал и умею доказывать, что асимптотически проходит. На 30 тестах 10009 работает 2.2 на сервере

У меня локально перебор на 30 тестах из чисел 90011 работает 2 сек. Запустил в "Запуске", работает 4.8 сек, печаль:(

Ну я упихал тупейший перебор — только на последнем уровне рекурсии вручную всё рассмотрел, а не как в общем случае. На худшем тесте успевало с запасом в 3 раза.

Оно упихивалось без следующей оптимизации?: Сначала выберем числа в последнем столбце и последней строке. Они должны содержать только цифры 1379, таких простых чисел всего 249, а не 9000+.

Будем ставить числа сверху вниз построчно. Тогда каждый раз все зависит от цифр, стоящих слева от свободной части. Делаем четыре динамики для разной заполненности матрицы с перебором по простым числам. Итоговая <<сложность>> — 10000 на количество простых. Работает за 1.5 секунды, каждый запрос за O(1).

Я тоже писал перебор. Было две идеи по оптимизации (написанных): 1) перебираем только нижний треугольник, в последней строчке — только числа 123579 (2 и 5 перебирать нужно из-за того, что они сами простые) 2) после того, как заполнили матрицу, можно за O(n^2) найти количество способов поставить цифры на диагонали. Для этого для всех чисел длины n-1 и для каждой позиции от 0 до n посчитаем количество способов вставить цифру в это число на эту позицию так, чтобы получилось простое.

Есть еще одно отсечение — после построения первых нескольких строк проверить, что количество способов поставить цифры на диагонали не равно нулю. Это я не добавил, потому что пришлось бы кучу индексов пересчитывать. На 30*10007 и без этого работает меньше полсекунды локально на моей не очень быстрой машине.

Я написал 2 оптимайза:

• ставим только символы которые могут продолжить наш префикс

• запоминаем ответы, которые уже знаем(потому-что не пашет только на некоторых тестах)

У Вас тоже электричество во время раунда отрубили?

Жадно, сортим, сперва в порядке убывания стоимостей табуретки, потом как угодно карандаши. Потом первый k-1 предмет кладем в отдельные корзины и остатки как придется

Кажется, должно работать: Если табуреток меньше k, то в каждую корзинку по табуретке, а остальные корзинки как угодно. Если табуреток ровно k, то, опять же, в каджую корзинку по табуретке. Теперь надо распихать карандаши, причём выиграть мы уже ничего не можем -- только проиграть. Поэтому положим все карандаши вместе туда, где самая дешёвая табуретка. Если табуреток больше k, то выберем из них k самых дорогих, а остальные будем считать карандашами.

Вроде легко решается, после системного тестирования посмотрим моя логика была такой:

1) если табуретка стоит дешевле карандаша, то скидку на карандаш ты не получишь, только на табуретку 2) если табуретка стоит дороже карандаша — получишь скидку на карандаш, но это совсем не выгодно

Из 1,2 следует, что лучше сделать как можно больше корзин, которые содержат лишь 1 табуретку, причём выбрать для этого самые дорогие табуретки.

Забиваем k-1 корзин самыми дорогими табуретками. Если табуреток меньше, чем k-1, то в оставшиеся корзины раскладываем по 1 карандашу. И в последнюю k-ю корзину сливаем все оставшиеся табуретки + все оставшиеся карандаши.

UPD: Столько минусов, а ведь алгоритм верный, АС =)

Например, в этот раз задача D была не самой лёгкой.

ИМХО, это только добавляет хаос.

Объясните мне. Понятно что делать раунд рейтинговым для участников вне конкурса, которые треть раунда не могли ничего сдавать — бессмысленно и не надо. Понятно что, нет никаких причин не делать раунд рейтинговым для участвовавших в конкурсе (ну не из-за кривого чекера по А точно). Так в чём вопрос?

А из-за чего нерейтинговый то?

my O(nk) (c++ too) passed in 390ms without any optimisations. Seems, your solution isn't O(nk) or has very big constant factor

My careful O(nk) passed in 190 ms. O(nk)s differ :)

My O(nk) solution in Pascal passed in 410 ms.

A dfs for each node times out when the graph is dense.....

My O(nk*log(n)) solution passed system tests)

нет, ну реально, кто-то мог изменить свою тактику, порядок решения задач, в зависимости от разбалловки. UPD пересмотрел правила, про стандартную разбалловку ничего нет) тогда вопрос: теперь ее не будут объявлять перед раундом никогда?