Послалось, когда удалил половину ненужных инклудов и using namespace std.

I am too receiving the same problem ...

Now I had "access denied" too, but using the "Submit" tab (rather than submitting from problem page) helped.

Same here!

Спираль размера k+2 — это квадратик минус спираль размера k минус еще одна клетка. Спиралей куб, каждую пересчитываем из спирали меньшего порядка за O(1). Перебрали все, сказали ответ.

Заметим, что квадрат размера k лежит в середине квадрата k+4. далее понятно

Пусть d[r][c] -- сумма в спирали размера k - 2, начинающейся в клетке (r, c); nd[r][c] -- то же самое для спирали размера k. sum(r, c, k) -- сумма в квадрате размера k; a -- исходный массив. Тогда nd[r][c] = sum(r, c, k) - a[r + 1][c] - d[r + 1][c + 1]. Так можно пересчитывать d от k - 2 к k и каждый раз проверять все ячейки. Сложность O(n·m·min(n, m)).

хм, а я начинал с каждой клетки раскручивать спираль с центра... раскручивал не по клеточкам, а отрезками и когда на очередном витке получалась корректная спираль, то проверял с ответом... сложность O(N³), но отнимать спиральки круче, у меня более косячное решение...

на ТЛ?

На тупом проходе по обеим строкам, что получало TL, например, на тесте:

2000000000
R
R

B: 4 4 .#.. ..## .#.# ..#. нельзя решать for i 1-n for j 1-m

на В ломали на ТЛ видимо тестами 1000 1000 где последняя строка заполнена точками (и подобное)

Все-таки это задача D :)

Ты еще и не прочитал что это D, а не С:)

what kind of tests?

What's the corner case for A? I saw a lot of hacking.

I don't tnink it shows that problems are tricky. Just somebody can't understand that naive algos are slow enough.

Чуть-чуть случаев. Разбили на две доли. Либо в обеих долях количество вершин делится на три (тогда очевидно), либо в одной остаток 1, в другой — два. Будем считать, что в первой — один.

Теперь если в первой доле есть вершина, не соединённая хотя бы с двумя из второй, убиваем этот треугольник, дальше — очевидно. Иначе в ответе, если он есть, бывают только тройки из одной доли или тройки ("2 из первой", "1 из второй"). Очевидно, что вторых троек будет 2 по модулю три, иначе не сойдутся остатки. Также в ответе, если он есть, можно сделать так, чтобы вторых троек было ровно две. Отлично. Нашли все вершины из второй доли, несоединённые хотя бы с двумя из первой, взяли две любые, выкинули два треугольника, дальше — очевидно

Раскидаем каким угодно образом наши города по берегам. Обозначим количество на городов на левом берегу a и на правом берегу b. Тогда если , то ответ очевиден (разбить на тройки на берегах). Если , то поменяем города берегами, тогда станет . Теперь попробуем найти на левом берегу город, у которого нет моста с двумя городами на правом берегу. Если такой имеется, то удалив эту "троицу" переходим к случаю когда . Вот, а теперь на чем всех ломались. Рассмотрим тест:

6 4
1 2
3 2
4 5
6 5

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

me too :)

Have you read the Announcement?

Can you explain how do you find shortest path with dfs?

For problem B, unsuccessful solution was Dijkstra with O(n^2 + m). On 1000 1000 with all #: n = 10^6, m = 2 * 10^9. 2 * 10^9 + 10^6 is TL.

DFS was even a more stupid idea, i think.

А зачем использовать Integer? Оно только между угловых скобок нужно, в остальных случаях int не хуже

list.remove((Integer) i)

Condition on ages doesn't look like "no 2 members have ages with difference greater than k", but like "each age of the member of the group should have difference no greater than k with group leader".

tourist, не, не слышал.

У меня B 2 раза упала на претесте 6, потом перечитал условие, оказалось, забыл, что надо -1 выводить, если нет решения -_-

One cute way of solving C without using the "shape" array is to define a spiral of size 1 as simply a single square. The recurrence then follows quite naturally for larger spirals.

Жирным выдели, чтобы в глаза бросалось. А то вдруг еще не заметят — и не снимут...

И так снимут;)

+1. Меня на ней ещё и взломали =(

Зачем извращаться с дейкстрой? Сила BFS с нами.

Я вот мог в красные пойти, благодаря таким вот Дейкстристам, Флойдистам и т.д. Но вот затупил во второй, тоже (сначала просто жадность написал)... И этим умножил свое итоговое место на 2.

И это хорошо!

Граф же невзвешенный!

+

Присоединяюсь к просьбе!

// а я думал, что оно автоматически открывается после окончания систестов, нет?

Все админы пошли спать наверное, других вариантов нету...

Чего?

Какое отношение это имеет к прошедшему контесту?

Традиционная рубрика "Вопрос по теме" :D

True story

It's kind of pointless to use Dijkstra when your graph only contains edges of weight 1. ;)

There was no need to write Dijkstra, especially with heap. Didn't you think about any simpler solution?

The complexity of Dijkstra with a heap is O( log(|V|) x (|V| + |E|) ) I think that the usual Dijkstra solution has |E| around 4x4x1000x1000 and |V|=4x1000x1000 (There is a node for each pair between each cell and each of the 4 directions. And for each of those nodes, there are 4 edges towards other nodes in case the cell it is a column).

Your complexity estimation seems to be |V|x log(number of cells), quite smaller. O( log(|V|) x (|V| + |E|) ) is 5 times larger and yields 9 digits.

СВОИ задачи? С каких пор они принадлежат КРОКу, если авторы (как я думаю) никакого отношения к КРОКу не имеют?

Возможно, лист по памяти раскидывает. Попробуйте вектор.

Нет проверки цвета строки (столбца) при добавлении в очередь, из-за этого в худшем случае в ней будет n*m элементов вместо n+m и общая сложность будет O(n*m*(n+m))

у list'a в g++ size() за линию работает, возможно из-за этого