I encourage you to implement it (it shouldn’t be that big, should it?) and test it against the above testcase :)

Let’s wait a bit.

http://lmgtfy.com/?q=acm+icpc+world+finals+2012+schedule

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

Сводим к стандартной задаче подсчета суммы целых частей (a*x+b)/c по x от 0 до n-1.

Yeah, now I understand — it looks like the selection system is quite prone to this kind of thing happening.

When I was a participant at the Russian IOI camps, there was about 12 days on average that decided the team, not 2, so it was much more stable and most gaps were more than one problem.

Yeah, it’s a pity that IOI selection was decided on that :(

But how come it’s just one problem that decides who gets on the team and who doesn’t? How many problems in total affect the selection?

Apparently there was a technical problem with the recording, and most probably it’s lost :-( We’re trying to see if we can recover it from backups, but most probably it’s gone. Sorry.

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

Yes. Meanwhile, you can ask and vote for questions at http://goo.gl/eoWf0 :)

Ну то есть, отвечая на второй вопрос — для подсчета time про третьего вообще забываем.

В этом сэмпле никто никого не может поймать — они же на цикле? Поэтому все time равны INF.

Считать time примерно так — построим ту часть графа, начинающуюся в вершине B, которая является деревом — т.е. как только мы доходим до цикла, помечаем эту вершину как “выход” и дальше не идём. В этой части есть ровно одна вершина, откуда стартует A — либо где он сейчас, либо где он появится. Подвесим часть за неё, тогда нужно на пути от B до корня понять, докуда B ещё может дойти, и из всех этих вершин найти самого глубокого ребёнка, считая глубину цикла INF.

В G зашло в дорешивании следующее:

1) Пусть time(X,Y) = INF, если игрок X не может поймать игрока Y, и максимальному времени, сколько Y может сопротивляться, если X может поймать Y. 2) Тогда пусть win(A) = time(A, B), если time(A, B) < time(C, A) (вроде как естественное условие, но может кстати и без него будет работать?..) и time(A, B) < time(C, B) (иначе C может "встать между A и B и добиться ничьей), и INF иначе. Аналогично для win(B) и win(C). 3) Тогда если среди win есть единственный минимум, то он и побеждает в игре для троих, иначе ничья.

Выглядит правдоподобно, но это далеко не первая итерация, и все предыдущие тоже выглядели правдоподобно :) Может у кого-то есть объяснение или более простое работающее решение?

У меня все было ровно так же до момента внимательного взгляда, ага. Надо его прокачивать, похоже :)

Сорри, что все еще не допираю. Новые ходы ведь появляются во всех местах начиная с b?.. Или ты имеешь в виду, что нужно посмотреть, что b+1 проигрышная, дальше понять, что тогда до 2b+1 опять будет чередование, потом опять две проигрышных, и так далее, а потом заметить что прыжки на b^2 и больше ничего не меняют? Пожалуй, да, так можно было сделать :)

Интересно, какое соотношение тех, кто так сделал и тех, кто увидел закономерность в ответах :)

Ну я так и сделал, но вот закономерность увидел небыстро. Может если бы выписал для b=2 а не b=10 было бы легче и правда :)

Можно на “ты” :) Я про решение подзадачи, когда есть ним с одной кучей и можно брать степени b. Доказательство SkidanovAlex выше уже прочитал, и правда просто. Остался второй вопрос — откуда может прийти в голову что важна четность остатка от деления на b+1 :)

Ага. 80 минут ее решал, когда решил наконец, решил забить на раунд пока не поздно :)

Очень интересно, как это придумали люди — у меня получилось только методом внимательного всматривания в ответы и только за час :) Там какое-то простое соображение, или хотя бы какое-то простое доказательство?

Она только финалистам похоже видна, да и результатов систеста там нет.

По штрафному времени :) Как в ACM.

Oops, I’m terribly sorry — the scoreboard contained a name in unknown language, but now that I look closer, it’s indeed in Korean.

Apparently Po-Ru doesn’t have a Codeforces account.

Ну пусть f(x) и g(x) два многочлена таких, что f(x)-f(x-1)=g(x)-g(x-1) для всех целых x. Тогда нетрудно заметить, что f(x)=g(x)+C (пусть C=f(0)-g(0), тогда f(1)-g(1)=f(0)-f(0)+f(1)-g(0)+g(0)-g(1)=f(0)-g(0)+(f(1)-f(0))-(g(1)-g(0))=f(0)-g(0)=C, и так далее.

Выводится несложно, Вася Астахов вот например рассказал:

Пусть P_k(n) — это сумму k-ых степеней от 1 до n. Тогда P_k(n)-P_k(n-1)=n^k. Продифференцируем обе части: P’k(n)-P’k(n-1)=kn^{k-1}=k(P{k-1}(n)-P{k-1}(n-1)). Откуда P’k(n)=k*P{k-1}(n)+C, и надо всего лишь найти два коэффициента.

Ээ, не понял. На кубке запрещено пользоваться Интернетом, какая разница есть инет на локальных компах или нет?

Если бы можно было пользоваться интернетом, мы бы сегодня часа полтора-два точно сэкономили.

О! Скажи, результатов ждать в ближайший час или ложиться спать?

Да, пруф вроде верный. Из него кстати следует (да в общем и так понятно), что можно вместо бесконечности сделать 2, тогда точно нет проблемы с ТЛем.

С ходу не знаю, скорее всего как-то можно добиться лексикографической первости в каком-то смысле :)

Может, нужно просто все остальные ребра сделать бесконечной пропускной способности, тогда они не попадут в разрез?