Discussion @ 1221. Malevich Strikes Back! @ Timus Online Judge

vgu Is there better solution then O(n^3) for each test? [4] // Problem 1221. Malevich Strikes Back! 31 Oct 2008 02:27

How I can do it on 0.001?

Edited by author 31.10.2008 02:29

Partisan Oops. There was error . It will be O(n^3) // Problem 1221. Malevich Strikes Back! 16 Jun 2009 00:31

Edited by author 16.06.2009 00:42

ConanKudo Re: Is there better solution then O(n^3) for each test? [2] // Problem 1221. Malevich Strikes Back! 8 Aug 2010 09:21

Mine is O(N^2)

Giorgi Dzamashvili Re: Is there better solution then O(n^3) for each test? [1] // Problem 1221. Malevich Strikes Back! 1 Nov 2013 01:17

How do you do ?

Solver Re: Is there better solution then O(n^3) for each test? // Problem 1221. Malevich Strikes Back! 11 Jun 2026 21:35

I track w0[i][j] as length of longest horizontal stride of a[i][j]==0 starting at i,j (0 if a[i][j]==1), symmetric for w1[i][j]. Now w1[i][j] defines the length to be tested (as 2*w[i][j]+1), this is done by descending downwards. At first it seems to be O(N^3) but due to nature of the pattern you won't descend all that frequently, so I believe it's O(N^2), and it gave 0.001 AC in C++

Discussion of Problem 1221. Malevich Strikes Back!