10824 - Regular Polygon

sclo · 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.

little joey · 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.

Hadi · 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.

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

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

PiM · 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 · 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.