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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

10824 - Regular Polygon

Post by stubbscroll » Wed Mar 09, 2005 4:31 pm

In case some people didn't notice it, this problem seems to have been rejudged and the contest ranklist is changed. I just checked the ranklist and noticed it was different. During the contest no-one got AC, but after rejudge there are 30-something AC's. So, if you got WA during contest, you can check if you got AC and stop looking for non-existent bugs in your code.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Wed Mar 09, 2005 5:10 pm

Excuse me. What's the expected complexity of the algorithm? Is an O(n^2) solution what the judge wants? Thx~ :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Wed Mar 09, 2005 5:14 pm

Observer wrote:Excuse me. What's the expected complexity of the algorithm? Is an O(n^2) solution what the judge wants? Thx~ :wink:
My solution is O(n^2) with some optimizations, and runs in 0.2 seconds.

[edit] Sorry, but my solution is actually O(n^3), still with optimizations.

ReiVaX18
New poster
Posts: 11
Joined: Mon Mar 29, 2004 11:53 am

Post by ReiVaX18 » Wed Mar 09, 2005 10:01 pm

Hi!
I am trying to solve this problem but only obtain WA. I sorted the points by their angle and searched the candidates to form the polygon using lower_bound(). I think this should be correct but I always get WA.
I generated an input with points of the form (cos(2*PI/2000.0), sin(2*PI/2000.0)) and get the correct result (4 500, 5 400, 8 250, etc.) and tried other inputs. Is there a problem with the 1e-8 accuracy? Do you have other inputs?
Thanx;

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Mar 10, 2005 12:39 pm

I also get so many WA...... Please could anybody post some test data here?

Btw, what's the time limit for this task during contest? 2 seconds?

- EDIT -

Just got AC with an O(n^2) algorithm, without much optimization. That runs for ~3 sec, and I guess that's quite slow...... Will try to improve it after dinner~~ :wink:

- EDIT (2nd) -

With a one-line pruning statement I get down to 1.8 seconds. Probably won't put any more effort on improving that. May try O(n^3) instead. :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Diego Caminha
New poster
Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil

Post by Diego Caminha » Wed Mar 16, 2005 1:58 am

Maybe there's a problem in the judge data. After many WA I got accepted just chaging the way a calculated the radius. Instead of using the first x and y, I used the last ones. I did that after I found out that my program calculated differents radius by the simple formula "radius = sqrt(x^2 + y^2)". But shouldn't all them be the same size since they are in the same circle?!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Mar 16, 2005 3:37 am

Depends on what you mean by "different".. they're the same for some epsilon..

Diego Caminha
New poster
Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil

Post by Diego Caminha » Wed Mar 16, 2005 6:22 am

By different I mean: fabs(r1-r2) > 1e-8. Maybe epsilon could be larger, but that was the only value I tested. And it was enough to make my solution wrong!

But if it isn't a problem in the judge data, then get it as a warning to the ones who are getting WA.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Wed Mar 16, 2005 1:05 pm

You can avoid computing radii at all - there's function atan2, which gives angle by point's coordinates - exactly what your solution might need. And the standards require it to be as accurate as possible.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat Apr 09, 2005 8:59 pm

Can anybody explain what is the O(n^2) or O(n^3) algorithm for this problem. I've used an O(n^3 lg n) algrotithm and got AC in ~.2 s and currently 5th in the ranklist. Thanks in advance.

Sanny

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Tue Apr 12, 2005 10:50 am

The O(n^3) solution is just like this:
- sorting all points O(n lg n)
- for k from 3 to n,
- - for j from 1 to n
- - - loop to see if a k-gon with pt j is possible

The O(n^2) one is just a modification of that, with a table. This solution is good in the sense that you don't need any optimization to get it within time limit.

With the online judge, it's not uncommon that O(n^3) codes outrun O(n^2) ones. For instance, in Q10667 Largest Block, my O(n^3) solution managed to get 0.00.006s, faster than most O(n^2) submissions. :D
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Wed Apr 13, 2005 4:07 pm

The O(n^3) solution is just like this:
- sorting all points O(n lg n)
- for k from 3 to n,
- - for j from 1 to n
- - - loop to see if a k-gon with pt j is possible
In checking whether a k-gon with pt j is possible, you have to check n -j points, isn't it? I'm not sure but I have a feeling that my (k-1) * lg(n-j) binary search would be faster than that. May be I'll try that later.

Sanny

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Fri Apr 14, 2006 5:41 pm

Hello all!

I'm trying this problem and always get WA :cry:, I think that a precision problem, I hate it.
But by other hand, my time is 6.000+ secs, and my algorithm is O(n^2), and I have seen that many people have a time less 1 sec.
Could anyone explain his/her algorithm or give me a good hint to reduce this time?
Some test cases will be appreciated too :D

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

Post by Hadi » Mon Aug 14, 2006 6:54 am

I get TLE with an n2log(n) solution :(

Edit: Now, getting WA with an O(n2) solution :(

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

Post by Hadi » Mon Aug 14, 2006 8:18 am

I finally got AC for this one.
If anyone needs testcase for this problem, use the following code:

Code: Select all

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
int main()
{
	ofstream fout("10824.in");
	for(int n = 14; n < 30; n++)
	{
		fout << n << endl;
		for(int i = 0; i < n; i++)
		{
			double b = i * 2.0 * acos(-1.0) / n;
			cout << b << endl;
			fout.precision(10);
			fout.setf(ios::fixed);
			fout << cos(b) << " " << sin(b) << endl;
		}
	}
	fout << 0 << endl;
	return 0;
}

Post Reply

Return to “Volume 108 (10800-10899)”