10824 - Regular Polygon

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Sep 08, 2006 9:08 am

how is it possible with O(n^2), i think you need to have O(n^2 lg n)
But anyway, my O(n^2 lg n) solution takes about 0.4 secs.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Sep 08, 2006 10:35 am

IMO complexity analysis for this problem is not easy and I believe most big-ohs reported in this thread are not true, so don't be blinded by them. Bottom line is the time you get from the judge, and I think 0.4 seconds is not too bad.

PS. I tried to analyse my solution, but couldn't get it quite right. I believe it's O(N^3.lnN), but part of it relies on probabilistics, and then it gets over my head... Also the amount of 'noise' (points that don't lie on any polygon) has a big influence on the runtime; and only the problemsetter nows how much he put in. So my suggestion is: don't bother.

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

Post by Hadi » Fri Sep 08, 2006 11:48 am

Mine is O(n^2) I think. Littlejoey, I am sending my code to you via a PM.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Sep 08, 2006 1:14 pm

Hi Hadi,
You're right, it's O(N^2).

PiM
New poster
Posts: 2
Joined: Fri Dec 08, 2006 11:33 pm

Post by PiM » Tue Dec 12, 2006 8:39 pm

HI!Does anyone has the solution of the Matrix Matcher Problem H on C++???If yes,PLEASE,send it to me.I need so much.

alterdeus
New poster
Posts: 1
Joined: Tue Dec 26, 2006 12:49 pm

Post by alterdeus » Tue Dec 26, 2006 12:52 pm

HI! Does anyone has the solution of the Regular Polygon Problem E on C++ or C#? If yes, PLEASE, send it to me. I need so much.

Post Reply

Return to “Volume 108 (10800-10899)”