Еще бы сессию отменить во время Евро

ну еще бы, он, наверное, и сам смотрит евро)

contests are rated normally :-/

vse deleted

As you wish, my lord.

здесь не любят егэ)

Держи нас в курсе

ЕГЭ по физике? Не, не слышал.

Почему-то почти всегда в начале анонса раунда есть в конец заминусованные комменты. =)
Теперь пришло моё время. :(

Всё-таки это была плохая идея во всех смыслах этого выражения.

The authors believe so.

No, non-descending :)

Почему нет?

Мне тоже... Если я не ошибаюсь, то задача, которая ну очень похожа на С была на каком-то ВКОШПЕ. И вторая баянистая...

Первая? По Вашему рейтингу могу предположить, что Вы во втором диве, и с уверенностью могу сказать, что первая задача была легкая. Нужно было чуть-чуть подумать и порисовать на листике. А можно и без листика совсем :)

wo ca

А как это делается хотя бы за квадрат?

Я пускал дейкстру из всех порталов одновременно, когда до какой то вершины уже дошли от другого портала, то добавлял соответствующее ребро в новый граф. А потом в этом новом графе искал миностов. Можно доказать что алгоритм Борувки на таком графе будет выдавать такой же миностов как и на правильном графе (когда все ребра есть).

Сперва идем к ближайшему порталу. Потом поддерживаем расстояние от множества взятых порталов до каждой вершины. Понятно, что каждый раз надо брать ближайший портал (примерно потому же, почему работает Прима). Можно заметить, что при обновлении расстояний каждая вершина срелаксируется не больше двух раз.

Запустим дейкстру, подвесив все телепорты за фиктивную вершину ребрами веса 0, из фиктивной вершины. Получим дерево кратчайших путей, если можно начинать из любого телепорта. Утверждается, что в качестве ребер графа, состоящего из телепортов, достаточно взять ребра исходного, концы которого лежат в поддеревьях разных телепортов, а вес положить равным d[u] + d[v] + weight.

если круг поместится то выигрывает 1, иначе 2: 1-ый всегда сможет сходить симметрично относительно центра после хода 2-ого

Всегда побеждает первый. Второй побеждает только если монета изначально не лезет на стол. Эта задача из книжки "Математикон" задачи Кенгуру.

Вроде, если помещаеться хотя бы одна тарелка, то виигривает 1, потому что он ставит в центр, а дальше ходит по симетрие к ходам 2.

Первый рисует окружность в центре, а далее ходит центрально симметрично. Понятно, что такая стратегия не работает только тогда, когда нельзя положить ни одной окружности. Т.е. если а и b больше либо равны диаметру, то первый, иначе второй.

Проблема с ответом infinity. Надо проверять не только a[0], а и b[0]. Если их произведение положительно — ответ "Infinity", если же отрицательно — "-Infinity".

Я думаю что-то вроде этого:

#.#
...
###
#S#
#.#

Такая эвристика по отбору решений мне шесть раз дала неудачный взлом вместе с тринадцатью удачными :-)

Странно. У меня 3 * n и 3 * m претесты не проходило.

За o(n * m) решается, как я понял. Запускаем обход, если дошли до края, то проверяем, есть ли с противоположной стороны проход. Если да, то Yes, иначе No. Правильно или нет? Если да, то очень печально, буквально пары секунд не хватило

UPD. Лажа

Можно загнать и с 3*Н*3*М:
Делаем волну на увеличенном поле, но добавим ход с краев в другой край, формально: сделаем таблицу цикличной.

7 9
#.#.#.###
#.#.#...#
#.#.###S#
#.#...#.#
#.###.#.#
#...#.#.#
#.#.#.#.#

Это тест не только против Вашего решения, но и против моего (взломанного).

5 9
###.#.#.#
#...#.#.#
#S###.#.#
#.#...#.#
#.#.###.#
#.#.#...#

Не на COCI. На одном латышском сайте по программированию.

If at least one circle can be placed in the rectangle, then first wins, because he can place circle in the center and then play symmetrically. In other case second wins.

See this: http://codeforces.com/blog/entry/4708#comment-96099

I took few cases , and In every case If FIRST can place the circle inside the rectangle then He can win otherwise , He can not win.

Some idea might be thought like if there are even no of circles possible in the rectangle , then He can just place a circle midway of two circles ,,, Means He can always change the configuration for winning move.

more clearer : if in the optimal path , if there are even no of circles inscribed in rectangle , then First can change the path by placing a circle midway of two circles . otherwise FIRST will win because last movement will be of FIRST , because no of turns are odd .

No.

3 16
.##..##..##..##.
#...#...#...#...
S.##..##..##..##

No, example:
##.#
...#
.###
.#S.
##.#

I think if we can go to any of the 'S' of 8 adjacent grids then it "Yes"

only itself is sufficient..

У нас в диве у всех почти попадала...

Я решал по принципу Дирихле. Будем ходить по бесконечному лабиринту, отмечая (в хэш-таблице) те клетки, в которых мы были. Если мы побывали хотя бы в m·n + 1 клетках — значит, две из них соответствуют одной и той же клетке исходного лабиринта, выходим из поиска и говорим, что ответ — Yes. Иначе — No.

Я так делал:
Проверим, можно ли двигаться бесконечно далеко вправо.
Сожмем компоненты связности в вершины, рассматривать будем только те, в которые входит хотя бы одна крайняя клетка. Теперь добавим переходы через границы поля (ребра между соответствующими вершинами). Вверх и вниз переходить можно бесплатно, перейти вправо стоит -1, влево 1.
Теперь, если в полученном графе есть цикл отрицательного веса, мы можем уйти сколь угодно далеко вправо, иначе нет.
Точно так же проверяем остальные 3 направления.

А зачем быстрее?

Мой O(n^2 logn) зашёл, 270 мс на макстесте.

Ну, к примеру, можно отсортить все точки по x, потом написать процедуру solve(l,r,v), которая решает задачу для поддерева вершины v, используя еще неиспользованные точки, лежащие между l и r по иксу (в сжатых координатах). Эта процедура будет разбивать неиспользованные точки на отрезки с кол-вом точек, соответствующем кол-ву вершин в поддереве соответствующего ребенка v, а потом рекурсивно запускаться в этих отрезках.

UPD: упс, не зашло =(

А, собственно, как вообще её решать, раз то, что написал tunyash, неверно?

Кто, где?

may you explain your proof?

При перепосылке.