NTHCIR - Editorial

editorial
, , , , , ,
20

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

21

Nice! Thanks :slight_smile:

22

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?

23

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

24

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.

25

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
26

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:

27

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
28

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.

29

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.

30

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

31

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.

32

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

33

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

34

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

35

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

36

thanks, well explained.

37

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.

38

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

39

you have to print exactly upto 6 decimal places…