Discussion @ 1717. Eligibility Rules @ Timus Online Judge

svr n=1500 seems to big.. [4] // Problem 1717. Eligibility Rules 18 Oct 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

SkidanovAlex Re: n=1500 seems to big.. [3] // Problem 1717. Eligibility Rules 23 Oct 2009 12:17

Max-sum submatrix problem has O(N^2 log n) complexity
As I heard, it is enough for this problem

[SPbSU ITMO] WiNGeR Re: n=1500 seems to big.. [2] // Problem 1717. Eligibility Rules 23 Oct 2009 12:54

How? I only know how to solve Max-sum submatrix problem with O(n) non-zero elements with this asymptotic

SkidanovAlex Re: n=1500 seems to big.. // Problem 1717. Eligibility Rules 29 Oct 2009 02:49

(deleted)

Edited by author 29.10.2009 04:19

SkidanovAlex Re: n=1500 seems to big.. // Problem 1717. Eligibility Rules 29 Oct 2009 04:18

OK, I see my mistake now :o)
N is number of non-zero elements, not the side of the matrix :o)

Discussion of Problem 1717. Eligibility Rules