My algorithm has o(n^5) complexity.
Is there any better solution?
If you have, please, send it me, klukva2@mail.ru. It is very interestingly.

Edited by author 22.08.2005 14:33

There is an O(n^4) algorithm.

Do you mean your algorithm is o(n^5), i.e. it is necessarily better than n^5?

Edited by author 29.08.2005 20:37

There are five nested cycles. Is it so strange? I think, many people have a same solution. Could you say something about O(n^4) algorithm?

f(n) = o(g(n)) <=> f(n) = O(g(n)) and lim f(n)/g(n) = 0 when n->infinity.

Let me guess your idea. You fix 5 sides and search the last one, right?

You should fix less. Fix the top and the bottom, and then you'll need to find the largest empty rectangle. This can be done in O(n^2).

No, I fix left, right, forward, backward and search the rest in O(n).Are you kidding? In case I know how to do it in O(n^2), I have guessed to the rest myself.
What you say looks like "Cricket field" from neerc (1235 on timus), but there are was squares (not rectangles) and also O(n^3) solution.
So I don't know, what you mean, sorry.

Edited by author 29.08.2005 22:56

You are right, that would be O(n^6)."Cricket Field" can be done in O(n * log n), but it's much more complicated.

Edited by author 30.08.2005 10:21