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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Jun 15, 2004 2:33 pm

Please give some test cases that can cause precision errors and is the angle at the center at most 45'??
help please.
"Everything should be made simple, but not always simpler"

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

Post by sohel » Tue Jun 15, 2004 2:58 pm

The angle at the center can be more than 45...

... infact I assumed the highest value to be pi - 1e-10;

One critical thing that comes to mind is if either C or N is equal to 0 then the output is zero straight away.

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

Post by misof » Tue Jun 15, 2004 3:59 pm

htl wrote: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.
Of course, the radius can be very long and we don't know an upper limit, therefore (I repeat myself) we do the following:
misof wrote:Set y=1. While the arc is too long, double y. Then bsearch with initial bounds 0 and y.
You probably overlooked/didn't understand the part "double y", meaning you should multiply y by 2 until the corresponding arc is short enough. In this way you find some upper bound (in logarithmic time) and then you can start searching in the range (0,y).

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Jun 16, 2004 7:57 am

Thanks Sohel for your help.
I got ac now. just expanding the limit of pi and checking c==0 and n==0. :lol:
"Everything should be made simple, but not always simpler"

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

10668

Post by udvat » Mon Jun 28, 2004 11:17 am

wud anyone plz check my code?

code has been removed
Last edited by udvat on Mon Jun 28, 2004 6:54 pm, edited 1 time in total.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Mon Jun 28, 2004 12:12 pm

I gave the following input to your program and it hanged.
  • 15 415 0.0044

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

thankx

Post by udvat » Mon Jun 28, 2004 6:57 pm

thank u very much shamim. I got accepted. :D

User avatar
Gigi's Baby
New poster
Posts: 19
Joined: Thu May 02, 2002 5:47 am
Location: Zhongshan (Sun Yat-sen) University

Post by Gigi's Baby » Thu Jul 29, 2004 4:13 am

I think it is easier to bsearch the answer.

assume the answer is x,
so r^2-(r-x)^2=(l/2)^2 => r=(l^2/x/4+x)/2;

angle= 2arcsin(l/2/r)
l'' = r*angle

compare l'' with l' to run the bsearch

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Aug 12, 2005 5:25 pm

Could someone post some critical test cases pls ?

I tried almost everything, I mean binary search on the
center angle, on the radius, on the answer. I also tried
different end conditions - still WA.

I even rewrote my C++ program in Java and still WA.
The C++ program uses long double and the Java
program uses double as there is no long double
in Java.

The interesting fact is that my program only runs for 0.000
or 0.002 secs before getting WA. So it should be some
obvious problem which still I do not discover for the moment.

Any ideas are welcome :) Thanks in advance.

P.S.
I hate posting code so I am not doing it for the moment.
Although I am sure it is some very very small bug.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Aug 12, 2005 9:59 pm

I got ACC, do not bother to answer me.

I just want to make a remark that could be of some
use in my opinion. My problem was the following one.

I was calling the function abs() with a long double argument.
My environment is VS .NET so I have as a built-in function
long double abs(long double)
Unfortunately when such code gets executed on the Judge's
Machine it actually produces a call to
int abs(int). In one of the emails from the Judge I suddenly
got a strange warning saying:
"03830241_24.c:34: warning: `long double' used
for argument 1 of `abs(int)' "

which made me suspect what I described above.

After writing on my own one new function
long double absLD(long double)
and after calling that function instead of
long double abs(long double)
I managed to get ACC immediately.

That was the reason I was getting all the time WA.
My code has just been behaving in a completely
different way on Judge's machine than on my machine.

Good luck to everyone !

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

10668 why wronged

Post by ibroker » Fri Nov 11, 2005 10:40 am

I got two equation.

L' = (1+nC)L = 2rθ ---- (1)
L = 2rsinθ ---- (2)

2rθ/(1+nC) = 2rsinθ
-> θ = sinθ(1+nC)

I dirrerenciate this equation.
so 1 = cosθ(1+nC)
-> θ = acos(1/(1+nC))

so I could know radious 'r' using equation (2) or (1)
so I could got a correct answer
BUT!!! may be this method is a wrong.
I can't have correct answer in example data case.

PLZ teach me why this method incorrect.

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

Re: 10668 why wronged

Post by Observer » Fri Nov 11, 2005 7:02 pm

Hi,

Of course this method doesn't work!

Consider θ = 2sinθ
Using your method, we get 1 = 2cosθ
=> θ = pi/3
but then 2sinθ = sqrt(3), i.e. your method fails...

And the reason why it fails is obvious. For a given t,
1. f(t) = g(t) does NOT imply that f'(t) = g'(t).
2. f'(t) = g'(t) does NOT imply that f(t) = g(t).
These can be seen easily from a graph.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

Re: 10668 why wronged

Post by ibroker » Mon Nov 14, 2005 12:17 pm

//Observer thanks
I got ACC but I have one more question.
I use bsearch to find out of theta.
But I got WA. because I use 'long double'
I don't know why 'long double' was wrong, and 'double' was correct.
I only change 'long double' of 'double'. and I got ACC.
Why?

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

Post by ayeshapakhi » Fri Mar 23, 2007 7:32 pm

i'm getting wa..
i used bisection for the centered angle made by the chord...
someone pls tell what i'm missing...

Code: Select all

#include <stdio.h>
#include <math.h>

#define err 1e-10
//deleted after acc.
thanks.
Last edited by ayeshapakhi on Fri Apr 06, 2007 4:45 pm, edited 1 time in total.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

10668 wa

Post by ayeshapakhi » Thu Apr 05, 2007 8:52 pm

Pls someone provide me some testcases.
it seems tough to avoid precision errors...

i would be highly thankful..

Post Reply

Return to “Volume 106 (10600-10699)”