ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1304. Parallelepiped

question(+)
Posted by Kit (Vologda SPU) 22 Aug 2005 12:59
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
Re: question(+)
Posted by Nick Permyakov 29 Aug 2005 11:40
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
Re: question(+)
Posted by Kit (Vologda SPU) 29 Aug 2005 15:22
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?
Re: question(+)
Posted by Nick Permyakov 29 Aug 2005 20:36
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).
Re: question(+)
Posted by Kit (Vologda SPU) 29 Aug 2005 22:53
Nick Permyakov wrote 29 August 2005 20:36
Let me guess your idea. You fix 5 sides and search the last one, right?
No, I fix left, right, forward, backward and search the rest in O(n).
Nick Permyakov wrote 29 August 2005 20:36
This can be done in O(n^2).
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
Re: question(+)
Posted by Nick Permyakov 30 Aug 2005 10:13
Kit (Vologda SPU) wrote 29 August 2005 22:53
Nick Permyakov wrote 29 August 2005 20:36
Let me guess your idea. You fix 5 sides and search the last one, right?
No, I fix left, right, forward, backward and search the rest in O(n).
You are right, that would be O(n^6).
Kit (Vologda SPU) wrote 29 August 2005 22:53
Nick Permyakov wrote 29 August 2005 20:36
This can be done in O(n^2).
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.
"Cricket Field" can be done in O(n * log n), but it's much more complicated.

Edited by author 30.08.2005 10:21