Архив форума

а как по задумке автора нужно решать грязь? дейкстра (для редких сетей) с хитрыми весами (1 единица тапок = 500*500 метров)?

Да нет же, здесь Волна. Правда чуть похитрей обычной :)

Я решал поиском в ширину с двумя очередями для чистых и грязных клеток - пока не кончились клетки в одной очереди, не брать их из другой. Зашло без проблем.

а на случайном тесте оно будет быстрее, чем обычная волна?

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

Кстати, боюсь, что в такой формулировке (N<=500) задача не зайдет на Тимус (где timelimit=1.00) с хорошими тестами. Там сложность алгоритма - чистый куб. Просто наше жюри ловило одни 'плохие' решения, и пропускало другие...

а не N*N*log N ?

Это следует понимать как
а) решение жюри не заходит на тимусе?
или
б) у жюри плохие тесты?

У жюри плохие тесты :) . На некоторых тестах авторское решение работает около 3-х секунд. На Тимусе timelimit - 1 сек.

Это наверное у участников была сложность n в кубе. :) Хотя у поиска в ширину сложность n квадрат.

Очень сильно подозреваю, что обычный поиск в ширину там не проходит! По крайней мере, все солюшены, которые я видел, имели сложность O(n^3).

Объясню ситуацию.

Во-первых, решение, которое предложил Шухман, на очном контесте не зашло бы - у нас было точно такое же :) . Дело в том, что на Тимусе нет последних тестов (оргкомитет не досмотрел?), на которых валится такое решение, я уже сейчас добавил один такой тест (Шухману предлагаю убедиться :) ), реальные добавлю позднее. Решение жюри эти тесты, само собой, проходит.

Во-вторых, на этих самых больших и завальных тестах решение жюри работает 4 секунды и получает MLE (ест 34 Mb !!!), мое решение - 2 секунды и ест 3.9 Mb памяти.

Предлагаю
1) жюри исправить солюшены на эту задачу, могу подсказать как избавиться от МLE :wink:
2) поднять Timelimit до 5 секунд, если не найдутся еще более завальные тесты :D

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

Ага, помнится даже клариф приходил: холодильник и компьютер находятся на разных клетках :D

Ну убедился. А маленьких завальных тестов не существует? Интересно, чем такое решение неправильно.То есть пока можно даже не пытаться решать - все равно не пройдет...

Пожалуйста. Обычная волна - не работает.
7 5
1 1
2 4
10000
12220
12221
12221
12221
12221
11111

Спасибо большое. Все понял.

Итак, возражений со стороны оргкомитета нет, поэтому я сделал следующее:
1) подправил условие в соответствии с тестами (очень хотелось их оставить без изменений!). Было: "The computer and the refrigerator are in different squares.". Стало: "The computer and the refrigerator are not on the squares marked with 0." Особого смысла в первом условии нет, а вот второе имеет значение (даже clarif такой был)
2) закачал все оригинальные тесты. Теперь набор тестов на Тимусе и на реальном контесте совпадают.
3) оставил без изменений ограничение по времени (1 сек) и поднял по памяти (6 Мб). Почему я это сделал? Потому что у меня есть решение за O(N*M*log(N*M)), которое работает 0.5 сек и ест 4.5 Мб памяти на новых тестах (http://acm.timus.ru/status.aspx?space=1&pos=574618). К сожалению, решения жюри не работают при данных ограничениях, да и вообще сделать эту задачу какой-либо волной врядли удастся - моя самая быстрая реализация работает 2 секунды. Зато теперь задача стала интереснее!

Жду ваши мысли по этому поводу.

Эх, так хотел разобраться, что у вас за волна. :) А теперь придется делать Дейкстру с очередью по приоритету. :(

Да тут нет секрета! Я могу рассказать свое решение с волной, оно лишь в реализации отличается от решения жюри. Делаем две очереди, в одну попадают только клетки с '1', в другую - с '2', и опустошаем их по очереди (то же самое, не прадва ли?). Но каждая клетка может попадать в очередь неоднократно.
В псевдокоде для общего случая можно записать так:

if dist[x]>new_dist then

    dist[x] = new_dist

    queue <= x

вместо обычного для поиска в ширину

if not used[x] then

    dist[x] = new_dist

    queue <= x

В любом случае оба варианта теперь не годятся :lol:
А годится алгоритм Дейкстры на куче. Причем здесь 8-ичная куча эффективнее обычной двоичной - это становится ясно, если решить соответствующую оптимизационную задачу. На практике работает на 15% быстрее.
Спасибо за идею Павлу Наливайко (см. форум на Тимусе). :wink:

Что-то молчит Стас... Буду я отвечать :)
Кто-то может вразумительно объяснить, почему не проходит обычная волна с двумя очередями?

Делаем так:
Для каждой клетки храним 2 числа: Reboots и Distance.
Инвариант: Если клетка помечена волной, то Reboots - минимальное количество переобуваний, за которое можно до этой клетки добраться, а Distance - минимальное количество шагов, при таком значении Reboots.

Если удастся поддерживать такой инвариант, то волна по каждой клетке пройдет только один раз. То есть сложность будет N*N.

Поддерживать же этот инвариант проще простого. Собственно алгоритм такой: Из клетки с компом пускаем волну. Причем клетки того же цвета, что и комп, кладем в 1-ую очередь, а остальные во вторую. Сама волна берет очередную клетку из 1 очереди, пока она не пуста.
Понятно что в результате получаем, что ВСЕ клетки, до которых можно дойти за 0 переобуваний побывали в 1 очереди, а во второй остались НЕКОТОРЫЕ клетки, до которых можно дойти за 1 переобувание.
Меняем очереди местами и снова пускаем ту же волну. и тд и тп пока обе очереди не станут пустыми.
На i-ом шаге мы полностью помечаем все клетки, до которых можно дойти за i-1 переобувание. И больше их никогда не трогаем. Причем поскольку на каждом отдельном шаге пускается самая наиобычнейшая волна, то Distance будет минимальным при данном количестве переобуваний. Т.о. инвариант поддерживается.

Может я чего-то тут важного не вижу? Почему N^3? Зачем по каждой клетке несколько раз бегать?

:? Да не может волна работать O(N*M). Посмотри на тест

7 5
1 1
2 4
10000
12220
12221
12221
12221
12221
11111

Здесь клетка (2, 4) попадет во вторую очередь с неоптимальным значением Distance => ее надо будет посетить еще раз.

Или может объяснишь почему Дейкстра с количеством итераций порядка 24 млн работает 0.5, а волна с 250 тысячами итераций работает очень и очень долго. Попробуй сдать задачу на Тимус при нынешних ограничениях волной. Кстати, если нехватает памяти используй stl-скую очередь - с ней у меня прога всего 3 Мб расходовала.

P.S. Вот бы на контесте такие ограничения поставить! Совсем не так бы задачу сдавали :wink:

Все! Теперь понял. Да, действительно не канает...
Однако, волна остается! Только структуру данных надо поменять с очереди на хип :) То есть очередная обрабатываемая клетка должна быть с минимальным Distance...
А это уже сильно на упомянутую Декстру на хипе смахивает...

А вообще, интересно, почему мы не сообразили, что волна тут не работает...

Да уж.. Еще одна не до конца развитая идея... Одно утешает: Сколько бы команд ее сдали бы, если бы были жесткие тесты с таймлимитами? Команды 3-4? ;) А так - целых 13! :)))

Так это и есть Дейкстра!

Факт! И я, как можно заметить, и не спорил :))
Просто, подчеркнул, что в алгоритме достаточно исправить самую малость - подменить хранилище :)

Что-то я не заметил этой темы раньше, исправляюсь.По-моему, это просто непонимание алгоритма. Ну и что, что клетка попала в очередь с неоптимальным значением? Надо искать не первое попадание в очередь, а полностью опустошить обе очереди, в конце у всех клеток будут оптимальные значения. Клетка может попасть в очередь не один раз, но не больше раз, чем у нее соседей. А если вести две волны (или две очереди, как описано выше), то "выходить" из этой клетки придется только один раз. А вообще, волна работает за время, пропорциональное количеству ребер (а не вершин, и не квадрата числа вершин, и тем более не куба). А ребер у нас сколько? Не больше 8*число вершин, т.е. 8*M*N. Т.е. принципиально волна работает. Реализованный мною алгоритм не оптимален по скорости и памяти, но я ведь и не программист :D
Изначально предполагалось отсечь решения которые идут совсем неоптимально - сначала помечают клетку как достигнутую за 100 переобуваний, потом как за 99 (и запускают новую волну из неё), потом за 98 и т.п. Надеюсь, это удалось. Остальное несущественно.

А доказательство?

Я провел небольшое исследование решения с двумя очередями, вот результат.
На одном из тестов клетки обновляются аж до 125 раз! Казалось бы O(N^3), но не понятно почему. Я проанализировал этот тест и понял откуда берется число 125, а также как его увеличить. Посидел и смастерил тест размером почти 500 x 500, на котором максимальное число обновлений составило 8508. При этом волна работала 2 минуты, в то время как Дейкстра не более 0.5 сек. Можно с уверенностью сказать, что это решение работает за O((N*M)^2).
Хотелось, конечно, для чистоты проверить сколько будут думать солюшены жюри, но в них, как оказалось, очередь реализована без расчета на такие тесты: один солюшен просто упал от переполнения очереди, а второй попросил столько памяти, сколько нет на моем компьютере. (Заметим, я не виню жюри в плохих солюшенах, просто не было расчета на такие тесты)

Что ж, со спокойной душой можно поднимать таймлимит на Тимусе до 2-х секунд - теперь никакая волна не грозит!Да, на контесте было несущественно, но на Тимусе пусть будут полноценные тесты.

Согласен, я был неправ :oops: Волна здесь неправильная т.к. на следующем этапе точек входа много, нужно следить, чтобы очередь волны была отсортирована по расстоянию, а это уже Дейкстра. Задача оказалась гораздо интереснее, чем про неё думало жюри. Владимир - молодец! Нам такого надо в команду организаторов, скорей заканчивай играть :wink:

на самом деле, есть все-таки способ решить задачу волной - мне подсказали его на разборе. Сначала двойной волной (двумя очередями) находим минимальное количество переобуваний для каждой клетки. При этом каждая клетка попадает в очередь не более одного раза (уже с оптимальным значением), поэтому сложность O(N*M). Потом уже ищем кратчайший путь с учетом количества переобуваний (условие связности для перехода на соседнюю клетку - количество переобуваний в ней равно или на один больше). Теперь каждая клетка попадает в очередь с минимальным числом и переобуваний, и просто шагов, значит, тоже сложность O(N*M). При этом никакой сортировки, хипа, Дейкстры не требуется, памяти на очередь нужно тоже O(N*M). Только волны здесь уже три (две вложенных в начале и одна потом), а не две, как я задумывал в начале.

Не могу не согласиться! Это решение правильное и работает за O(N*M). Вот такое и надо было зачитывать на контесте, а остальные отсекать.
Теперь на Тимус будут заходить 2 решения:
- двойная волна, описанная выше, O(N*M);
- модифицированный алгоритм Дейкстры, O(N*M*log(N*M)).

Может у кого-нибудь есть еще идеи?