Discussion @ 1492. Vasya's Dad 2 @ Timus Online Judge

Krayev Alexey (PSU) Did anybody have troubles with test#5 ? [18] // Problem 1492. Vasya's Dad 2 23 Oct 2006 23:23

Krayev Alexey (PSU) Re: Did anybody have troubles with test#5 ? [14] // Problem 1492. Vasya's Dad 2 24 Oct 2006 17:09

Consider test:
3
-15000 0
-14999 0
15000 1

is the output

Yes
-15000.000000 0.500000
-14999.000000 0.499983
14999.000000 0.499983
15000.000000 0.500000
-15000.000000 -0.500000
-14999.000000 -0.499983
14999.000000 0.499983
15000.000000 0.500000

correct ?

I mean if we output only 4 digits it turns into

Yes
-15000.0000 0.5000
-14999.0000 0.5000
14999.0000 0.5000
15000.0000 0.5000
-15000.0000 -0.5000
-14999.0000 -0.5000
14999.0000 0.5000
15000.0000 0.5000

[Ural SU] GetTester Re: Did anybody have troubles with test#5 ? [10] // Problem 1492. Vasya's Dad 2 25 Oct 2006 13:19

Yes. Both outputs are correct.

Vedernikoff Sergey Re: Did anybody have troubles with test#5 ? [9] // Problem 1492. Vasya's Dad 2 25 Oct 2006 14:29

Really mysterious test...

I can't find error in my program too...

Vedernikoff Sergey Re: Did anybody have troubles with test#5 ? [8] // Problem 1492. Vasya's Dad 2 25 Oct 2006 17:27

Oh! What's a bug! The following test helped me to fix it:

Sample input:
7
-5 2
-4 1
-3 -1
-2 -4
-1 -6
0 -7
5 0

Sample output:
Yes
-5 1.0
-4 -0.2
-3 -1.9
-2 -4.1
-1 -5.8
0 -7.0
1 -5.8
2 -4.1
3 -1.9
4 -0.2
5 1.0
-5 1.0
-4 1.2
-3 0.9
-2 0.1
-1 -0.2
1 0.2
2 -0.1
3 -0.9
4 -1.2
5 -1.0

Krayev Alexey (PSU) Re: Did anybody have troubles with test#5 ? [7] // Problem 1492. Vasya's Dad 2 25 Oct 2006 23:29

My program passes this test but still wa5

svr Re: Did anybody have troubles with test#5 ? [6] // Problem 1492. Vasya's Dad 2 26 Oct 2006 00:24

Friens!. I had no problems with 1492 because used module of fracrion numbers(1274) or in other word used exact arithmetics. Dont use rouunding , epsilon but just exact type.

Krayev Alexey (PSU) Re: Did anybody have troubles with test#5 ? [3] // Problem 1492. Vasya's Dad 2 26 Oct 2006 00:53

I use exact arithmetics.

svr Re: Did anybody have troubles with test#5 ? [2] // Problem 1492. Vasya's Dad 2 26 Oct 2006 08:46

Then troubles owing to too complicated cod. Problem 1492 is for youngsters. Bounds 15000 are very small and may be worked with by using array F[30000] of fractions. For founding corner point x2 it may be used simplest idea of sliding triple (x-1,y1),(x,y2),(x+1,y) with checking y2*2==y1+y2

Vedernikoff Sergey Re: Did anybody have troubles with test#5 ? [1] // Problem 1492. Vasya's Dad 2 27 Oct 2006 15:54

I used real arithmetics, and got AC. My be, it is overflow when use exact arithmetics? In any case, problem can be accepted in both cases.

Edited by author 22.06.2007 14:05

svr Re: Did anybody have troubles with test#5 ? // Problem 1492. Vasya's Dad 2 27 Oct 2006 17:05

In our case we form fraction value
F(t)=y[i]+(t-x[i])*(y[i+1]-y[i])/(x[i+1]-x[i])
for t in [x[i];x[i+1]] and after that form
F1[t]=(F[t]+F[-t])/2 and F2[t]=(F[t]-F[-t])/2
t in [x[0],-x[0]].
Denumenator and numenator dosn't more than 30000*30000=
900000000 . By using __int64 as fraction components
we will in safety from overflow

[Ural SU] GetTester Re: Did anybody have troubles with test#5 ? [1] // Problem 1492. Vasya's Dad 2 28 Oct 2006 23:26

It is not the truth. It is possible to do it without exact arithmetics. The author's decision works without it.

svr Re: Did anybody have troubles with test#5 ? // Problem 1492. Vasya's Dad 2 29 Oct 2006 00:37

Wu mustn't repeat author solution. But when we use exact arithmetic we can formulate a problem as some statement on finite set and answer will definite and under control

pperm Re: Did anybody have troubles with test#5 ? [2] // Problem 1492. Vasya's Dad 2 19 Aug 2007 23:58

I have trouble)) I use exact arithmetics and get AC.
Me help test:
5
-3 4
-1 3
0 2
1 1
3 0

Yes
-3.0000 2.0000
3.0000 2.0000
-3.0000 2.0000
-1.0000 1.0000
1.0000 -1.0000
3.0000 -2.0000

Denis Koshman Re: Did anybody have troubles with test#5 ? [1] // Problem 1492. Vasya's Dad 2 19 Aug 2008 19:28

Thanks, helped me to find a bug :) I wrote 0 if original function does not cross (0;0). Also I had some problems inside finding mid-point, including X=0 case.

Edited by author 19.08.2008 19:46

bsu.mmf.team Re: Did anybody have troubles with test#5 ? // Problem 1492. Vasya's Dad 2 5 Feb 2013 20:24

Solved without exact arithmetic or eps.
Just replace all divisions by multiplications :)

Edited by author 05.02.2013 20:25

Azrail Re: Did anybody have troubles with test#5 ? [2] // Problem 1492. Vasya's Dad 2 28 Dec 2006 12:31

I used cpp double and eps=1e-9 and got WA5. When i changed eps to 1e-6 i got AC. Maybe it'll helps you.

xiaomengxian Re: Did anybody have troubles with test#5 ? [1] // Problem 1492. Vasya's Dad 2 21 Apr 2007 07:28

I used pascal extended and eps=1e-6 and got WA 12. When I changed eps to 1e-9 I got AC... How strange...

AlexF [USTU] Re: Did anybody have troubles with test#5 ? // Problem 1492. Vasya's Dad 2 14 Jun 2007 23:21

My eps in cpp double is 1e-9 - AC

Discussion of Problem 1492. Vasya's Dad 2