NTHCIR - Editorial

Were test cases weak? I used pappus chain n got 75 . Pappus chain is a special case I guess

Precision takes a toll when you are taking square roots so many times!

the floating results must always be accepted within 1e-6 relative error.

Did someone manage to get accepted this problem using solution no.2 form editorial? Iā€™m failing so far.
Maybe someone could help me? Please, take a look at my submission, e.g. function solve2_editorial.

Maybe, someone got it accepted using solution no.2? Could you please share your code?

p.s. Admins, Setter code is not available! Please, fix it!

@yash_15 i donā€™t get you, i tried casting the sqrt function to long double, didnā€™t work

Please help me with my code. My code fails on second test file in sub task 1. :confused: Thanks in Advance.
View my Code here!

How to proceed after an=((n*c1+C)^2-c2)/c1 to obtain C???
for eg for the test case
1
1 2 1 5
6 1 1 2
we get two values of C=-1.684,-3.316 by substituting n=3 and a3=1/r3 but none of these values hold for n=4 & a4.
plzz explain

it is similar to this problem whose solution is here. But what makes it interesting is the fact that the inversion about the circle at origin can be shifted by some amount delta .So, you have to use the radii of the circles r3 and r4 for calculating the shift and backtranslate from the smaller circles to find the radii of the nth circle. The formulas can be found here..
My submission is here.. It is a really cool concept.

2 Likes

The formulas(8) and (9) will be sufficient as mentioned in the wolfram link.

thanks, well explained.

@vijay_cipher could you provide more details on your solution? I am struggling with this single line:

yl=(.25*((1.0/r4)-(1.0/r3)))-rs;

As far as I understand this is the center of left most circle (Cā€™_3) after inversion. But do not understand how you derived this formula. Could you provide more details on it?

Thanks.

rb(i, 4, 2000) compute the radius of all circles from 5 till 2000. I also tried rb(i, 4, 2000000) and I still got wrong answer for subtask 1. I still couldnā€™t find the problem.

Nowhere it was mentioned that the solution will be accepted within 1e-6 relative errorā€¦

you have to print exactly upto 6 decimal placesā€¦

Why can we write

xn=xnāˆ’1+c1 as xn=nc1+C ?

If you have the curvatures of 4 circles you can get the curvature of the 5th circle easely by S*V, where
Ci=1/Ri, S is a matrix S=(1 0 0 0; 0 1 0 0; 0 0 0 1; 2 2 -1 2) and V=(C1 C2 C3 C4) initially. So we need the 4th line of S^n that is n(n+1) n(n+1) -n n+1. n=1 => C5

If you have 4 circle curvatures then u can multiply the vector of the curvatures with 4 matrices and generate all the possible circles in an Apollonian gasket. S is actually S3 and corresponds to a new circle tangent to the first, third and fourth circles.

Hey,
Was the formula for the 2nd subtask also available in google search? I hope not.

Every problem has a pre-requisite. If you know the concept of inversion, then you can solve this problem from scratch without using google.

2 Likes

Could you please provide a link to image or any thing related to how you found out the solution to the recurrence. I am stuck at some stepsā€¦or any strategy that i should try.

I used a simpler recursion to find the radius: note that circles C_n and C_{n+2} are both tangent to the triplets C_1, C_2, C_{n+1}, so \dfrac{1}{R_n} and \dfrac{1}{R_{n+2}} both satisfy the Descartes theorem equation for C_1, C_2, C_{n+1}. One easily gets that the sum of the roots of the equation is 2(-1/R_1 + 1/R_2 +1/R_{n+1}). We know one of the roots is 1/R_n and the other is 1/R_{n+2}, so \dfrac{1}{R_{n+2}}= 2 \left( -\dfrac{1}{R_1} + \dfrac{1}{R_2} + \dfrac{1}{R_{n+1}} \right ) - \dfrac{1}{R_n}. From here itā€™s easy to see that \dfrac{1}{R_n} is a quadratic in n and we plug in the given values to find the coefficients.

@bondoc, i also had the same concept and problem earlier. But according to the comments mentioned in the problem during the contest, the radius of the circle can increase after some interval. For similar figure you can refer to figure of Apollonian gasket. Also, see the first solution of lebron (link-http://www.codechef.com/viewsolution/7391329) he also used the same concept but with one difference as soon as the radius becomes so small that it is negligible, he starts to takes the reverse series again.

May be this helps.