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

vgu Is there better solution then O(n^3) for each test? [4] // Задача 1221. Malevich Strikes Back! 31 окт 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) // Задача 1221. Malevich Strikes Back! 16 июн 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] // Задача 1221. Malevich Strikes Back! 8 авг 2010 09:21

Mine is O(N^2)

Giorgi Dzamashvili Re: Is there better solution then O(n^3) for each test? [1] // Задача 1221. Malevich Strikes Back! 1 ноя 2013 01:17

How do you do ?

Solver Re: Is there better solution then O(n^3) for each test? // Задача 1221. Malevich Strikes Back! 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!