По словам Вани Метельского это баг

Уже исправили на :10

Все равно во всех календарях время фигурирует ровное.

Бывают какие то проблемы с ареной — обычно решаю перекачиванием jnlp файла. Может здесь тоже самое?

Календарь алгоритмических контестов — http://community.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth

Соревнования проходят в java апплете — Arena. Запустить ее можно нажав слева вверху изображение O(N)

(i-j+n)%n — плохая идея.

Я ломал 2 неверных жадняка (например движение только в 1 сторону) + вероятно падали на том, что можно получить индексацию по отрицательному индексу (т.к. r[i] <= 50, что может оказаться больше чем n).

return d[start — 1][ end — 1]; :(

Должна заходить динамика на битовых масках. Из ограничений суммарное число столбцов и строк (n) не больше 28. Переход делается за O(n) с маленькой константой. Если аккуратно писать, должно зайти наверное.

UPD. Минусующим и всем вопрос, как же правильно делать :)

Заметим, что ответ — это сумма вероятностей того, что мы ещё не закончим к i-му шагу, по всем i от 0 до бесконечности.

Вероятность того, что мы закончим к i-му шагу можно посчитать формулой включений-исключений. Сначала сложим вероятности того, что каждая строка или столбец будут непокрыты. Каждая из них это (1-s)^i, где s — сумма вероятностей этой строки или столбца. Затем вычтем то же самое для всех пар (там s будет суммой объединения), добавим для троек и так далее.

Теперь внесём внешнюю сумму по i внутрь формулы включений-исключений: sum((1-s)^i)=1/s.

Теперь переберём подмножество строк (если столбцов меньше, то перевернём сначала). Если мы зафиксировали подмножество строк, то наша сумма s — это константа плюс сумма непокрытых частей столбцов, которые войдут в подмножество.

Таким образом задача свелась к 2^12 таких задач: у нас есть n чисел ai и константа C, нужно найти сумму (-1)^(размер подмножества X)/(C+сумма-ai-по-всем-i-из-подмножества-X) по всем 2^n подмножествам X.

А это можно решить динамикой: посчитаем число способов набрать каждую сумму четным и нечетным числом слагаемых. Ну или можно упростить, и сразу считать первое минус второе, тогда динамика получается как обычный рюкзак, только вместо "+=" пишем "-=". См. моё решение в арене :)

Сложность в районе 2^12*9*150*13.

Расскажите, что за жадность.

У меня зашел обычный обход дерева в глубину, в котором я считал, сколько путей осталось непокрытыми в поддеревьях, продолжал их важными ребрами и сливал пары таких путей для разных потомков, увеличивая ответ. Интуитивно (формально индукцией надо доказывать, что ли?), если покрывать пары путей разных потомков при первой возможности, то непокрытых путей в каждом поддереве будет не больше одного, и ребро к родителю корня поддерева либо продолжает такой путь, если там лампа выключена, либо обрывает его, если она уже включена.

It's obvious that if first player chooses some cell (x, y), second player chooses a cell with a maximum distance to (x, y). So we need to minimize the maximum distance from other cells to chosen. We can precompute the d[x][y][x2][y2] — the minimum distance from (x, y) to (x2, y2). Then just iterate over all cells, and for each cell compute maximum distance from other cells to chosen. Then just get minimum. That's all.

You can use a simple SPFA to pass it, it's an easy problem! We know that first person always choose the start point to minimize the longest shortest path from it. So we need to determind every point in the map and let it be the start point. Then we can use a SPFA to calculate all shortest path from this point and find the longest. At last we should return the smallest longest shortest path amaong all the nodes. We can think it just an O(N*N) algorithm. Because of N is at most 1600, so we can pass this problem now!

там есть магическое условие if(dist[v] == -1)

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

I think it depends. Since the order of solving doesn't matter in Topcoder if you have enough time to solve both, either way is fine.

If you solve easy problem first, you will get some certain points as well as a kind of warmup before going to the next ones.

If you choose to start with the medium — like what I usually do, you will avoid lack of time for it in some cases, but some tricky 250 probably become more challenging if you switch into them too late. To prevent this from happening, use the scoreboard wisely. However, the main reason I stick with this strategy is because I do not learn much from solving a 250 only. Some times it works, the other you may end up with no problem solved. Yet I think keeping doing this way would help you improve your solving skill faster, as least in my own experience.

Well according to me it is always a good idea to first attempt the 500 problem because at the start you can give time to a better question as compared to a 250 point problem which on an average just requires at most 5-7 minutes (if it is not a tricky one).Well you can also take the help of the scoreboard to make a guess what is the level of the question and switch to the other question if required ....

 swap(dx,dy); dy *= -1;

Nice magic trick. Thanks!