| 1 Трохачев Андрей Вадимович, 31 января 2020 г. 18:40:14 |
Решил за O(nlogn) через Multi-Source bfs. Можно ли решать задачу за линию?
Любой bfs не даёт log в O большом.
|
|
|
|
|
| 2 Неизвестный, 12 сентября 2019 г. 18:07:54 |
| Решил за O(k*f) k-кол-во единиц,f-кол-во нулей
|
|
|
| 3 Виденеев Илья Владимирович, 16 августа 2019 г. 15:17:18 |
| тут даже графы не нужны, тупо перебором решается, как задача "Вирусы"
|
|
|
| 4 Смирнов Илья Сергеевич, 07 августа 2019 г. 11:37:35 |
| Подскажите,пожалуйста,как выйти на сложность O(N*M) ? Разве не будет оптимальным запускать BFS от каждой единицы и обновлять значения в клетках таблицы? Тут получается O(k*N*M),k - кол-во единиц
|
|
|
| 5 Якина Ангелина Ивановна, 15 июня 2019 г. 15:29:54 |
Возможно, я как-то неправильно поняла условие задачи, но я писала Дейкстру с кучей. Как итог - Accepted (хотя мне кажется, эту задачу можно решить, например, шириной).
Если все длины рёбер равны (как в случае этой задачи), то вместо алгоритма Дейкстры конечно же можно использовать поиск в ширину.
|
|
|
| 6 Сидоревич Антон Валерьевич, 28 августа 2017 г. 15:03:11 |
| Можно эту задачу сделать более сложной с решением за O(N*M)
|
|
|
| 7 Зубашев Степан, 27 июля 2016 г. 19:01:01 |
| Решил и с BFS, заодно его распробовав. На такой малой выборке разница заметна только по сложности кода ;)
|
|
|
| 8 Зубашев Степан, 26 июля 2016 г. 21:32:25 |
Решил грубо. Кажется: O(N^2 * M^2). При данных ограничениях с огромным резервом проходит перебором. Без двумерных массивов, векторов и пр. Просто массив координат точек, массив координат единиц. Для каждого 0 сравнение с каждой точкой, минимальный результат в вывод.
Судя по ответам админа не комильфо. Пожалуй стоит решить ещё и через БФС.
|
|
|
| 9 Глейх Андрей Артурович, 11 октября 2012 г. 11:02:33 |
Ну что я могу сказать: при сравнении одного и того же алгоритма на Java и на C++ STL стало мне очевидно что STL рулит. Там где у Java TLE, С++ запросто проходит. А асимптотика алгоритма ниже указана Нурланом
У Нурлана странная асимптотика
|
|
|
| 10 Тулегенов Нурлан, 14 июня 2012 г. 10:50:05 |
У меня получилось O(k0 * k1) где k0 - количество нулей k1 - количество единичек
Иными словами, в худшем случае, когда нулей и единиц поровну, то получается сложность алгоритма O(N^2*M^2), т.е. плохая у Вас асимптотика, но при данных ограничениях может теоретически пройти. Но я полагаю, что скорее всего Вы неверно асимптотику посчитали. При использовании BFS получается сложность O(N*M), и очевидно лучшей асимптотики быть не может.
|
|
|
| 11 Тест Тест Тест, 31 октября 2011 г. 18:18:37 |
lol, ограничения надо до 1000 поднять.
Чтобы только решить было возможно через BFS с очередью?
|
|
|
| 12 Ситдиков Рузаль Раилевич, 14 октября 2010 г. 19:58:20 |
| Bfs рулит)))
|
|
|
| 13 Козлов Валерий Викторович, 28 июля 2010 г. 20:21:59 |
| И эта задача тоже по-моему больше подходит в раздел ДП.
|
|
|
| 14 Sharipov Marat Kayratovich, 18 марта 2008 г. 7:18:38 |
извените, а по диагонали тоже считать за растояние или через боковые стороны? например: 2 2 0 1 0 0. ответ будет 1 0 2 1 или 1 0 1 1. Плз хелп ми.
По диагоналям считать не надо, это понятно из условия задачи.
|
|
|
| 15 Эхсанов Абдулхаким, 15 октября 2007 г. 13:55:44 |
4 4 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 какой будет ответь?
такой: 3 2 1 0 2 2 1 0 1 1 1 0 0 0 0 0
|
|
|
