NTHCIR - Editorial

What a beautiful question… got the same recurrence but was not able to prove it…

Also, Codechef please give the 2nd test case (1st subtask) values and solution as many got WA in this (including me)…

Later found matrix while surfing net, which can also help to solve for nth radius using Matrix exponentiation.

I have a doubt. The recursion is completely fine and theoritically we will get the right answer using it. But as test cases can be as large as 10^7 and the radius can be a real number as large as 10^12, the final answer can contain more than 20 digits (including decimal digits). So how are you guys getting the accuracy???..

Consider the test case:
10000000
1 2 1 1
99999999999.999999 r2 r3 r4

(since ‘m’ is 1 and B is 1 ‘n’ will always be 1 and so values of r2, r3 and r4 doesn’t affect the answer and so we can give any values for now)

I ran the setters solution on this test case and it gives wrong answer. The correct answer should be 999999999999999990 because we have to add r1 10^7 times.

Please clarify my doubt.

1 Like

I was wondering why this code didn’t work for the first subtask? It uses Descartes formula, yet it still gave WA. Can anyone tell me where is the mistake?

LL n, p, m, b;
double r1, r2, r3, r4, t1, t2, res;
vector R;

int main() {
//freopen(“test.in”,“r”,stdin);
//freopen(“test.out”,“w”,stdout);

int T;

scanf("%d", &T);

scanf("%lld%lld%lld%lld", &n, &p, &m, &b);
scanf("%lf%lf%lf%lf", &r1, &r2, &r3, &r4);
R.PB(r1); R.PB(r2); R.PB(r3); R.PB(r4);

r1 = 1.0 / r1; r2 = 1.0 / r2;
rb(i, 4, 2000) {
    r3 = r4; r3 = 1.0 / r3;
    t1 = r2 + r3 - r1;
    t2 = (r2 * r3) - r1 * (r2 + r3);
    r4 = t1 + 2.0 * sqrt(t2);
    r4 = 1.0 / r4;
    R.PB(r4);
}

res = 0.0;
while(T--) {
    //scanf("%d%d", &n, &q);
    n = (n * p) % m + b;
    res += R[n - 1];

    //printf("%lld\n", res + K[n][k]);
}

printf("%.9lf\n", res);


return 0;

}

please tell me why this did not pass even first sub task?

#include <iostream>
#include <cmath>
#include <cstdio>
 
typedef long long int ll;
typedef long double ldf;
 
using namespace std;
 
ll mulmod(ll a, ll b, ll c)
{
	ll x = 0;
	ll y = a%c;
 
	while(b>0)
	{
		if(b%2 == 1)
			x = (x+y)%c;
		y = (y*2)%c;
		b/=2;
	}
	return x%c;
}
 
int main()
{
	ll t;
	scanf("%lld",&t);
 
	ll n,p,m,b;
	scanf("%lld%lld%lld%lld",&n,&p,&m,&b);
 
	ll r1,r2,r3,r4;
	scanf("%lld%lld%lld%lld",&r1,&r2,&r3,&r4);
 
	ldf k1,k2,k3,k4;
 
	k1 = 1.0/r1;
	k2 = 1.0/r2;
	k3 = 1.0/r3;
	k4 = 1.0/r4;
 
	ldf ans = 0;
 
	for(ll x=1;x<=t;x++)
	{
		n = mulmod(p,n,m) + b;
		
		if(n==1)
		{
			ans += 1.0/k1;
			continue;
		}
		if(n==2)
		{
			ans += 1.0/k2;
			continue;
		}
		if(n==3)
		{
			ans += 1.0/k3;
			continue;
		}
		if(n==4)
		{
			ans += 1.0/k4;
			continue;
		}
		
		ldf z = k4;
		for(ll i=5;i<=n;i++)
			z = k2 - k1 + z + 2.0*sqrt(k2*z - k1*(k2 + z));
		ans += z;
	}
 
	ll ans1 = ans*10000000;
	ans = ans1/10000000.0;
	printf("%.6Lf",ans);
	return 0;
}

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

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!

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

@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