Обсуждение @ 1221. Malevich Strikes Back! @ Timus Online Judge

Is there better solution then O(n^3) for each test?

Послано vgu 31 окт 2008 02:27

How I can do it on 0.001?

Edited by author 31.10.2008 02:29

Oops. There was error . It will be O(n^3)

Послано Partisan 16 июн 2009 00:31

Edited by author 16.06.2009 00:42

Re: Is there better solution then O(n^3) for each test?

Послано ConanKudo 8 авг 2010 09:21

Mine is O(N^2)

Re: Is there better solution then O(n^3) for each test?

Послано ძამაანთ [Tbilisi SU] 1 ноя 2013 01:17

How do you do ?

Re: Is there better solution then O(n^3) for each test?

Послано Solver 11 июн 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++

Обсуждение задачи 1221. Malevich Strikes Back!