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

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

HotLog


 
[Вернуться к задаче]   1
  1  Давид Нигматуллин, 31 августа 2018 г. 20:38:05
     предлагаю указать, что прямоугольник с нулевой стороной, быть не может, потому что мне казалось что в крайнем случае можно ничего не брать, и получить 0
     Сделано.
  2  Японский шпион, 12 июля 2018 г. 5:57:26
     Kadane's algorithm, O(n^3).
  3  Мурашов Денис Андреевич, 08 июля 2018 г. 14:27:49
     Решение O(N^2 * M^2) не проходит по времени на Python (см. 8530435).
     И не должно проходить. Python может выполнить порядка 10^6 операций в секунду, а для указанной Вами сложности получается ближе к 10^8 операций. Не все задачи можно сдать на Python.
  4  Беляев Сергей Николаевич, 16 января 2016 г. 9:51:26
     
     Добавлены новые тесты. Все решения перепроверены.
  5  Скрынник Алексей Александрович, 09 июня 2015 г. 11:24:42
     Решил за O(n^3)
  6  Нуриев Наиль Дамирович, 25 апреля 2015 г. 10:01:16
     Советую сначала решить задачу №470.
  7  Костливцев Никита Алексеевич, 28 марта 2013 г. 9:37:11
     Прикольная задача...
  8  Иванов Александр Сергеевич, 25 июля 2011 г. 23:28:04
     Я непонимаю, как это задачу можно решить без перебора? Ведь в любом случае нам надо будет вычислить суммы абсолютно всех прямоугольников. И как же тут тогда применить динамическое программирование? Если не сложно, дайте хотя бы указание, потому что как я ни крутился, дальше 10-го теста не прошел. Можно конечно попытаться решить с помощью дерева Фенвика, но неужто иначе нельзя?
     Задача имеет достаточно простое решение со сложностью O(N^2*M^2), разумеется динамическое. Но конечно никто не запрещает использовать двумерные деревья отрезков, но это как то посложнее будет ....
  9  Балакший Андрей Владимирович, 22 июня 2011 г. 16:29:54
     Хм, придумал как решить только после задачи 470...
  10  Bruce Wayne, 16 марта 2011 г. 11:22:50
     3 3
1 1 1
1 -100 1
1 1 1
  11  Нагин Сергей Юрьевич, 04 сентября 2010 г. 20:37:39
     так-же просто можно решить и за Куб...
  12  Грачев Владимир Алексеевич, 07 октября 2009 г. 18:18:09
     Вот уж никак не думал,что ваш сервер осилит порядка 50 миллионов за секунду,и пытался решить за Н*М,пока не прочитал обсуждение!
     Да, просто операции простые, вот если бы там были умножения... Сервер наш не особо быстрый, но эта задача полезна для понимания оценки скорости простых операций. На хорошей машине может за секунду выполняться до миллиарда простых операций (например xor) :)
  13  Масюк Олег Юрьевич, 22 января 2009 г. 12:25:22
     Скажите как тут динамику применять?
     Динамика тут может использоваться для вычисления промежуточных результатов. Если догадаться для каких, то применить ее совсем будет просто.
  14  Ладик Артём, 12 декабря 2008 г. 19:28:36
     у меня O(n*n*m)+O(n*m*n*m) но на самом деле примерно в 80 раз меньше
     да, только так, но кто-то мне писал, что возможно n*m... меня это сильно пригрузило... не представляю как это возможно.
  15  Хохлов Илья Евгеньевич, 10 апреля 2008 г. 0:45:02
     Одна клетка может являться искомой областью?
     Конечно! Особенно, когда M=N=1 ;)
  16  Таран Александр, 01 декабря 2007 г. 18:36:54
     даже непонятно как решать.... динамическое программирование? полный перебор?... мда..
     Да, динамическое программирование тут нужно использовать. Задача легко решается со сложностью O(M*N*M*N) (в том плане, что нужно знать метод, а реализация простая), а полный перебор, это нечто вроде O(M*N*M*N*M*N), что абсолютно недопустимо. Я слышал, что эта задача может быть решена со сложностью O(M*N), но я сам не представляю как.
 1

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

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