ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1717. Правила допуска

n=1500 seems to big..
Послано svr 18 окт 2009 12:37
After sorting we have the problem of
finding maximal-sum submatrix
but it has O(n^3).
After additional thinking- all OK!
This is the way.For eaach row range [i1,i2]
it should  mantain set of nonzero columns
and number of such colums in mean must be 1-10

Pardon...Tle. Instead 1-10 really we have 500

Edited by author 19.10.2009 20:45
Re: n=1500 seems to big..
Послано SkidanovAlex 23 окт 2009 12:17
Max-sum submatrix problem has O(N^2 log n) complexity
As I heard, it is enough for this problem
Re: n=1500 seems to big..
Послано [SPbSU ITMO] WiNGeR 23 окт 2009 12:54
How? I only know how to solve Max-sum submatrix problem with O(n) non-zero elements with this asymptotic
Re: n=1500 seems to big..
Послано SkidanovAlex 29 окт 2009 02:49
(deleted)

Edited by author 29.10.2009 04:19
Re: n=1500 seems to big..
Послано SkidanovAlex 29 окт 2009 04:18
OK, I see my mistake now :o)
N is number of non-zero elements, not the side of the matrix :o)