Скорее речь об отсутствии токенов.

Токен — это возможность один раз увидеть полный фидбэк по задаче. В разных версиях может либо регенерироваться через 30 минут после использования, либо просто появляться каждые 30 минут и накапливаться. Нововведение с последних IOI, подробнее можно почитать в правилах IOI 2010/2011/2012.

Wow, that's interesting. So the rules placed here are wrong?

Really? If it's true, more people will take part in this contest (because people like me are too lazy to test their submitions well ;) )

12 for a single problem or for all?

Хороший вопрос. Я тоже не понимаю, как хотя бы до тестирующей системы добраться. Давайте, если кто поймёт что да как, отпишется об этом здесь?

Я лучше напишу 5 часовой контест)Вроде бы полезнее будет)

Лучше напишу CEOI в качестве тренировки перед IOI. Хороший контест, этих SRM'ов и так вагон и маленькая тележка, а такой только раз в году, можно и написать.

И действительно, правила как и говорил fhlasek.

У меня даже сайт не работает.

Они же вроде врубают её только на время контеста...

У меня сайт недоступен...

1. Читаем письмо от организаторов
2. Сам не знаю =)

У меня сейчас ничего не грузит уже минуты 3!

При этом он всё равно показывает username в заголовке... :D

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

Задачи в студию!

Старый добрый тур втёмную.

Может намекают что больше мы не успеем сдать)

Спасибо, друг!

Ты мой кумир

Спасибо огромное!

Всё правильно, все же задания доступны здесь?

Да!

На IOI-style контестах не бывает таблиц.

А таблицы так и не будет ?Неужели "таблиц не бывает" буквально?А списки?

да

Да, но, кажется, сэмплы ваша программа всё равно проходить должна.

It seems ok now.

UPD3: Contest server is veeeery slow so here is the mirror for the tasks (thx to popoffka): mirror

Результат доступен тебе сразу на страницах Result и ShowAllSubmit.

1. Не знаю
2. Zlobober попробовал, никакого эффекта.

circuit разве первая была, или ты это по своей нумерации?

Про квадрат с подгонкой:

• Просто квадрат, где берём отрезок O-точка и проверяем все другие отрезки с 0 на пересечения — если таких всего 2 — эта точка видна.
• Добавление break, если кол-во пересечений уже 3, не помогло, но тесты стали идти заметно быстрее, но всё ещё TLE.
• Перебираем другие отрезки не с 0, а с текущего-50. Внезапно взяло 40, пройдя -надцатые группы (видимо там много зигзагов рядом), но не пройдя 4ю.
• Посколько в 4й группе наверняка ограничение меньше, чем в -надцатых, был наудачу поставлен if — если N <= 10000, начинаем с 0, иначе с текущего — 50. Зашло — 45.

Поэтому, имхо, говорить полные результаты, где сабтаски не как на IOI, не есть хорошо.

А как решать race?

В race ацикличный граф ???

Ну у меня вышло так.

Сначала считаем ДП: a[i][j] — сколько макс. можно сделать этапов, если начать в вершине i и используя следующие j вершин после неё (j может быть и отрицательным, тогда это предыдущие, там всё получается наоборот, буду рассказывать только про следующие).

a[i][j] = max по к (a[k][длина [i+1..k-1]], a[k][длина [k+1..i+j]) + 1

Осталось, если можно делать пересечение со стартом.

Тогда, если мы знаем первую дугу S -> T, то она всё разделит на 2 половины, в ту которую мы зайдём первой, мы можем идти только в одном направлении, потом перейдя во вторую половину, и там уже идти как угодно.

Зафиксируем T и в какую сторону от Т мы будем сначала идти. Так как в первой половине мы можем идти только в одном направлении, получаем DAG, по которому квадратично считаем для каждой вершины самый длинный путь за который можно дойти из T в неё.

После чего, возможен такой O(N^4): теперь перебираем и S, а также путь X -> Y. Пояснение общего пути: S -> T -(в одном направлении как-то)-> X -> Y -> ... . Тогда, как дойти до X из T мы знаем, как дойти из Y, можем высчитать за константу по массиву a, и всё прекрасно.

Сокращаем до куба — не будем фиксировать Х. Если есть S, T и Y, то мы знаем первую половину, и нам всегда выгодно взять такой Х, чтобы он был в ней, есть дуга X -> Y и путь из T в Х — самый длинный. Соответственно, замечаем, что в этих условиях S никак не фигурирует.

Итого, перед тем как фиксировать S, для каждой вершины Y считаем величину b[Y][k] — максимальный путь до какой-то вершины X на диапазоне T, T+1, ..., k-1, k что есть путь X -> Y. b[Y][k] — это либо b[Y][k-1], либо Х — это вершина k. Получаем O(N^3).

Красотой это пожалуй не назовёшь, и во время еле заходит. 2 WA.

Да.
Но я думаю, там M*log(M) не зайдет. Я писал N*log(M): бинпоиск + жадник, то есть фиксирую кол-во, а потом самых старых пытаюсь взять.

У меня почему-то 95 и ВА только на первом тесте. Но, наверное, да. Только там надо делать за nlogn + m, но сложности это почти не добавляет.

Ого, заявочка на золото)

Как надо было пихать race чтобы получить сотку?

На каких тестах был WA? Мне так и не удалось от него избавиться...

писал в личку

In the beginning we're using dynamic programming: a[i][j] — what is the maximal amount of stages, if we're beginning in harbor i, and are using the next j harbors after i (j can be negative as well, in which case we're using previous j harbors, but the solution will have the same idea, so I'll speak about next harbors only).

a[i][j] = max by k in [i..i+j] (a[k][length of [i+1..k-1]], a[k][length of [k+1..i+j]) + 1

This is basically the solution if k = 0, and now we need to deal with the case when k = 1.

Then, if we know the first stage S -> T, it will divide everything in 2 pieces (at we will visit both of them). In the one we'll be visiting first, we can go only in one direction, otherwise we won't be able to cross to the other piece. Afterwards we will cross into the second piece, and we can go there as we want.

Imagine we fix T and the side which we will visit first (left or right). Because in that piece we can only go in one direction, we get a directed acyclic graph, for which we can compute for every harbor the longest path from T to it. We can do it for O(N^2).

Imagine the following O(N^4): we are now fixing not only T, but S and a new path X -> Y as well. The description of a total race is now as follows: S -> T -(in one direction)-> X -> Y -> ... .Now, we know how it is optimal to get from T to X, and we also can calculate for O(1) using previous DP how we need to go from Y.

Now, let's shorten it to O(N^3). We won't fix X now. If we know S, T and Y, then we know the first piece, and it is always optimal to choose such a X, so that it is in the first piece, the edge X -> Y exists and the path from T to X is the longest possible. We can notice that in that condition S doesn't figure at all.

So, before we fix S, for every harbor Y we calculate b[Y][k] — the maximum path to Y from some harbor X, where X is in interval {T, T+1, ..., k-1, k} and there exists a path X -> Y. b[Y][k] is either b[Y][k-1] or we get a new optimal X = k. Now all three parts of the case k = 1 are O(N^3).