NTHCIR - Editorial

@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.

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.

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-CodeChef: Practical coding for everyone) 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.

Nice! Thanks :slight_smile:

Can anyone post a nice link to better understand the concept of inversion ? There aren’t many tutorials about it clubbed with the programming category. Is it important?

What do you mean by complement circle? Also how to do you prove that complement of nth circle is (n-2)th circle

if u see by descartes theorem…for example initially u are given 4 circles…
1 outer C1 and three inner circles C2 C3 C4…now to make a new circle C5…u will put curvatures of C1,C2,and C4 in descartes equation which will provide…two solutions…as it is quadratic in nature…therefore one solution is the new circle…what will be the other solution…the one which was already touching C2 C1 and C4…and what was that? C3 ryt…therefore …C(n) and C(n-2) are complement circles…u can see this by drawing :smiley: …though the recurrence relation u guys made was easier to solve than this one.

Yes, this is the recurrence I used in the tester’s solution. Then I simply found the general term of the linear recurrence.

1 Like

I also have some doubts about precision :slight_smile: I was lazy to check it by myself. I had different solutions passing different tests - and I am not really sure that one which passed all tests is most precise :smiley:

I think the point was to see if we could figure out Subtask 2 using our algebra skills AND our knowledge of Descartes formula from Google.

2 Likes

You have to be very careful with your floating point calculations. I don’t think there was any test case in the original problem as brutal with precision as that (although I didn’t pass Subtask 2, so I don’t really know), but the second test case of Subtask 1 was hard with precision. I had to try multiple times to get my floating point calculations as precise as possible before I passed that test case.

Second test case of first subtask was probably wrong due to floating point errors. I also got WA on this test case for a long time until I finally fixed my floating point calculations and made them as precise as possible.

It was funny when one of my solutions was passing ONLY second case of subtask 2 but failing other 3 :smiley:

What does rb(i, 4, 2000) do? If it loops i from 4 to 2000, that was probably the problem because for Subtask 1, I think N_i could be as big as 3000.

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.

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

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

thanks, well explained.