Can I participate(unofficially, but rated) if I didn't qualified to 2nd round?

Btw do you know the reason for that restriction (only those who qualified)? Server load or something like that? Doesn't seem very fair.

topcoder.com/tc and arena aren't loading on my computer too.

it is working as for me, and people discuss past ipsc 2012 in chat

but site is down

Формат тот еще, да, но задача вполне номальная.

Насколько я понимаю, они не поддерживают vector<vector >, поэтому приходится так издеваться. Не первый раз такое, думаю, надо отнестись с пониманием. (Что-то верстка захавывает int).

У меня началась.

надо уменьшить что-то. это поможет потом.

d[18][10]=1

У меня этот семпл не проходил, т.к. некоторая дорога становилась равной -1.

"Что не так" — похоже, решение жюри :)

Upd: а с семплами всё ок, команды перекидывают землю одновременно, и землю чужой команды на том же ходу использовать нельзя.

Решение расскажи, иначе как понять, что в нем не так.

Аналогично, сидел прикручивал какие-то структуры, но ничего толкового не вышло

500: посчитаем сначала количество треугольников вида x[r] < x[g] < x[b], y[r] < y[b] < y[g] и x[r] < x[g] < x[b], y[r] < y[g] < y[b] в сумме. Это можно сделать, если отсортируем все точки по x, сожмем координаты по y, потом будем перебирать x[r] и поддерживать сумматор, отвечающий на запрос, сколько точек с координатами l <= y <= r. Если текущая точка (x[r], y[r]), то при c = sum(y[r] + 1, MAXY) к ответу нужно прибавить c * (c — 1) / 2. Далее из сумматора удалить точку y[r] и перейти к следующему x. Вот, а теперь из ответа нужно вычесть кол-во треугольников x[r] < x[g] < x[b], y[r] < y[g] < y[b] — т.е. кол-во 3-инверсий. Это известная задача, можно тем же сумматором посчитать.

500 — сожмем координаты, посортим точки по x. заведем 2 дерева отрезков с суммой, в первое из них положим все точки.

теперь идем снизу вверх (по x) и поддерживаем наши деревья отрезков так, чтобы в 1м были все точки выше, а вот 2м — все ниже (ну просто "перекладываем" из 1го дерева во 2е). и в процессе считаем 2 величины:

1. количество "любых" треугольников с углом в красной вершине
   x(r) < x(g) < x(b) && ( y(r) < y(g) < y(b) || y(r) < y(b) < y(g) )
   это T1.get(y_i, n) * (T1.get(y_i, n)-1) / 2;

2. количество треугольников где точки "на одной прямой"
   x(r) < x(g) < x(b) && y(r) < y(g) < y(b)
   это T2.get(1,y_i) * T1.get(y_i, n)

ну и в конце просто вычитаем 2е из 1го

Мне кажется, 500 можно решить и без дерева интервалов. Однако я, к сожалению, не успел дописать решение во время соревнования, поэтому, пожалуйста, скажите, если следующие рассуждения неверны.

Нужно понять, что нам надо посчитать количество всех возможных хороших треугольников, которое равно количеству всех треугольников минус количество плохих. А плохие бывают всего двух видов — когда у трёх точек монотонно увеличиваются сразу две координаты, и когда одна монотонно увеличивается, а другая уменьшается. Первый случай решается с использованием метода динамического программирования за O(N*logN), а второй — аналогично, только с инверсией одной координаты.

Многие (в т.ч. я) писали вообще за O(N⁵). Мне кажется, теоретически можно за куб, если заранее найти все рёбра, по которым возможен переход, но это уже много возни.

Я не знаю решения быстрее, чем за 5ю степень

Решили сделать вид что контеста не было?)

Ну топ117 достанется с гарантией. Увеличится за счет того, что есть люди попавшие туда несоклько раз.

Берем у каждого лучшее место, какое он занимал, сортим по нему. Первые 350 людей в списке — молодцы.

Для каждого береться лучшее место из раундов 2А, 2В, 2С. По ним делаеться общая таблица и первим 350 дают футболки.

Спасибо за хорошие новости. Не думал, что 112 места будет достаточно. В этом году как-то не получалось у меня с футболками, я даже второй раунд GCJ умудрился проспать, а тут за один день обеспечил себе футболки RCC и TCO.