Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1
  1  Вечер Даниил Леонидович, 05 октября 2019 г. 14:20:56
     Уважаемые админы,подскажите пожалуйста почему RE на 3 - ем тесте?
  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
 1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru