10668 - Expanding Rods

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

Moderator: Board moderators

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

10668 - Expanding Rods

Post by htl » Mon Jun 14, 2004 8:15 am

It seems that it's a easy geometry problem. I use Newton-Raphson Method to get the angle of the sector. But I always got WA. Could someone give some input?

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

Post by Observer » Mon Jun 14, 2004 8:33 am

Maybe you could try working on the displacement directly. Dunno if it helps...

Btw, I suspect that there are rods of zero length in the input, so you may think of treating this as a special case.

P.S. I got ~25 WAs before AC just because of a silly flaw in my rounding method... :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jun 14, 2004 9:03 am

I first tried solving the problem by doing a binary search on the radius of the circle, but wasn't able to get this accepted, despite being very careful with accuracy.

Then I did as Observer suggested and performed the search on the actual answer instead, which turned out to work fine.

I guess this is because near C*n=0.5 (the maximum value), the answer has a very sensitive dependence on the radius.

(And yeah, there are rods in the input with C*n > 0.5 and l = 0)

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

my suggestion

Post by sohel » Mon Jun 14, 2004 11:13 am

These are the two equations that I got...

L' = r * ang;
L = 2 * r * sin(ang/2);

where r = radius and ang = angle at the center..

Later I applied B.search on L'/L - ang/(2*sin(ang/2) )= 0 to find the value
of ang...

And finally answer = r - r*cos(ang/2);

I initially apllied -- while( fabs( low - high) > 1e-6) and it got WA.

but later I changed to -- while( fabs( low - high) > 1e-10) and it got AC.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

WA...surely some precision error

Post by helmet » Mon Jun 14, 2004 12:16 pm

Can anyone help me with this problem...Im getting WA and I know its precision

Code: Select all

Accepted
[/cpp]
Last edited by helmet on Tue Jun 15, 2004 7:06 am, edited 1 time in total.
Just another brick in the wall...

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

minor mistake

Post by sohel » Mon Jun 14, 2004 12:57 pm

Two mistakes in your code:

[c]
while(L>0||n>0||C>0)

[/c]

Suggestion : Input ends with three negative numbers.

[c]
while(theta>1E-6&&fabs(theta-thetad)>1E-10);

[/c]

change 1e-6 to 1e-10;

Hope it helps.
:wink:

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

WA still

Post by helmet » Mon Jun 14, 2004 2:03 pm

I changed to 1e-10 but I didnt understand the first comment bout 3 negative numbers.I assume all 3 must be negative to end.
Just another brick in the wall...

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: WA still

Post by CDiMa » Mon Jun 14, 2004 2:19 pm

helmet wrote:I changed to 1e-10 but I didnt understand the first comment bout 3 negative numbers.I assume all 3 must be negative to end.
Maybe you assume that but your prog doesn't ;)
Ciao!!!

Claudio

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Jun 14, 2004 3:45 pm

Nice one CDiMA :D

To helmet:
0 is not a negative number. :wink:

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Jun 14, 2004 5:14 pm

I used almost the same method as sohel, but using nr method. This code got TLE. This is my first code using nr method to solve the equation. Could someone give some advice on my code? Or using bisection could be better? I'm poor at computer numerical method and hoping someone to help me solve problems like this. :P

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jun 14, 2004 7:18 pm

htl wrote:I used almost the same method as sohel, but using nr method. This code got TLE. This is my first code using nr method to solve the equation. Could someone give some advice on my code? Or using bisection could be better? I'm poor at computer numerical method and hoping someone to help me solve problems like this. :P
My experience (learned through much frustration :)) is that NR is almost useless in contest problems like this, mainly because of stability issues. It's much easier to get a bisection routine working and stable, and for simple equation solving like this, you won't notice any speed difference.

So yeah, my advice would be to switch to bisection.

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

Post by Lars Hellsten » Mon Jun 14, 2004 9:30 pm

Per, I had the same problem during the contest. I did binary search on the radius, which is not precise enough. I guess if you have a really small difference like 0.0000001, the radius can be huge, and with the formula I used, that meant taking the cos of something very close to 0. Searching on the angle would have similar problems. But I got tunnel vision and didn't realize this. I prefer to think about algorithms, and not implementation details like FP precision. :-?

I do know someone who got the binary search on the radius to work, by using long doubles and implementing his own cos function. Wish I'd thought of that.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof » Mon Jun 14, 2004 10:56 pm

In the contest I wrote binary search on radius (or, more exactly, on the y coordinate of the center) using doubles and got it AC on the first attempt :)

Algorithm:
Handle cases where L' is near L and when it is near PI * L / 2.
Set y=1. While the arc is too long, double y. Then bsearch with initial bounds 0 and y.

When you have a fixed y, you compute the radius r=sqrt( sqr(y) + sqr(L/2) ). Note that r=y+x, where x is the answer. To compute the length of the arc, compute the angle using atan2.

My opinion is that precision errors may arise in boundary cases (especially in the case when y is almost zero). If you don't handle them separately, check whether your solution gives the correct answer in these cases.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Tue Jun 15, 2004 6:07 am

Setting the range of y between 0 and 1.... But I thought that the radius could be very long as well as y. Could you give me more guidelines? I still work on finding the proper range that I could do bisection.

helmet
New poster
Posts: 31
Joined: Tue Mar 02, 2004 11:55 am

yahoo

Post by helmet » Tue Jun 15, 2004 7:07 am

Thanks to my new found knowledge that 0 is not negative I got it AC...
Just another brick in the wall...

Post Reply

Return to “Volume 106 (10600-10699)”