Answers to: NTHCIR - Editorialhttps://discuss.codechef.com/questions/72678/nthcir-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/NTHCIR">Practice</a><br>
<a href="http://www.codechef.com/JULY15/problems/NTHCIR">Contest</a> </p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/adurysk">Adury Surya Kiran</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/mugurelionut">Mugurel Ionut Andreica</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/darkshadows">Lalit Kundu</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium-Hard</p>
<h1>PREREQUISITES:</h1>
<p>advanced maths, geometry, recurrences</p>
<h1>PROBLEM:</h1>
<p>We are given radius of circles $C_1$, $C_2$, $C_3$ and $C_4$ in the following image: </p>
<p><img height="20%" src="https://s3.amazonaws.com/codechef_shared/download/JULY15/NTHCIR1.png" width="20%"></p>
<p>Now, we are going to draw circles $C_5$, $C_6$ and so on in such a way that $C_n$ touches circles $C_1$, $C_2$ and $C_{n-1}$. Like as shown in the following image:</p>
<p><img height="20%" src="https://s3.amazonaws.com/codechef_shared/download/JULY15/NTHCIR2.png" width="20%"></p>
<p>Given upto $10^7$ values of $n$, find sum of radius of circle $C_n$ for all $n$.</p>
<h1>QUICK EXPLANATION:</h1>
<p>======================== <br>
Using Descartes' Theorem, if we have $3$ existing circles of curvature(inverse of radius) $a_1$, $a_2$, $a_3$, we can draw a $4^{th}$ circle of curvature $a_4$, touching all three circles such that $a_4 = a_1 + a_2 + a_3 \pm 2 \sqrt{a_1*a_2 + a_2*a_3 + a_1*a_3}$, where $a_4$ is negative if it represents a circle that circumscribes the first three. </p>
<p>Now, $n^{th}$ circle in our problem is formed by finding the $4^{th}$ circle touching circles $C_1$, $C_2$ and $C_{n-1}$. So, we can define our recurrence, solving which we get general term for the radius of $n^{th}$ circle.</p>
<h1>EXPLANATION:</h1>
<p>================ </p>
<p>One of the ways to solve this problem is via Descartes' Theorem. First, lets define what curvature of a circle is. </p>
<p>The curvature of a circle with radius $r$ is defined as $\pm \frac{1}{r}$. The plus sign here applies to a circle that is externally tangent to the other circles, like the red circle is externally tangent to the three black circles in the image. For an internally tangent circle like the big red circle, that circumscribes the other circles, the minus sign applies.</p>
<p><img height="20%" src="https://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Descartes_Circles.svg/500px-Descartes_Circles.svg.png" width="20%"></p>
<p>Descartes' Theorem states that if four circles are tangent to each other at six distinct points, and the circles have curvatures $a_i$ (for $i = 1, ..., 4$), then: </p>
<p>$(a_1+a_2+a_3+a_4)^2=2(a_1^2+a_2^2+a_3^2+a_4^2)$.</p>
<p>When trying to find the radius of a fourth circle tangent to three given kissing circles(circles that touch each other mutually), the equation is best rewritten as: </p>
<p>$a_4 = a_1 + a_2 + a_3 \pm 2 \sqrt{a_1*a_2 + a_2*a_3 + a_1*a_3}$</p>
<p>The $\pm$ sign reflects the fact that there are in general two solutions. One solution is positive and the other is either positive or negative; if negative, it represents a circle that circumscribes the first three (as shown in the diagram above).</p>
<p>Now, let's see how we employ this theorem to find solution to the problem. </p>
<p>We know that $C_n$(for $n \ge 4$) is formed as a $4^{th}$ circle tangent to three kissing circles $C_1$, $C_2$ and $C_{n-1}$, where $C_1$ is being touched by all circles internally. And also, the circle $C_n$ will touch all other circles externally, so we are interested in positive curvature of $C_n$. And, curvature of $C_1$ is $-\frac{1}{r_1}$.</p>
<p>So, we can write using Descartes' Theorem that $a_n = a_1 + a_2 + a_{n-1} + 2 \sqrt{a_1*a_2 + (a_2 + a_1)*a_{n-1}}$. Now, we can employ this recurrence to find $n^{th}$ circle, in $O(n)$. This will be enough to pass <strong>subtask 1</strong>.</p>
<p>For <strong>subtask 2</strong>, we need a constant time solution for each $n$, that means we need to arrive at a closed form of the $n^{th}$ term of recurrence. Let's see how we can solve this recurrence. Basically, our recurrence is:</p>
<p>$a_n = c_1 + a_{n-1} + 2 \sqrt{c_2 + c_1 a_{n-1}}$, <br>
where $c_1 = a_1 + a_2$ and <br>
$c_2 = a_1 * a_2$ </p>
<p>Here, we substitute $x_n$(a new recurrence) as $\sqrt{c_2 + c_1 a_{n}}$, which implies that <br>
$a_n = \frac{x_n^2 - c_2}{c_1}$ --------Eqn (1) </p>
<p>So, our recurrence is now $a_n = c_1 + a_{n-1} + 2 x_{n-1}$. In this equation, substitute $a_{n-1}$ and $a_n$ using equation $1$ to get,</p>
<p>$x_n^2 = x_{n-1}^2 + 2c_1x_{n-1} + c_1^2$, which is basically $x_n^2 = (x_{n-1}+ c_1)^2$. Now, this has greatly been simplified to $x_n = x_{n-1} + c_1$, whose general term can be written as $x_n = nc_1 + C$, where $C$ is an arbitrary constant, which depends on $x_1$.</p>
<p>Now, to find $a_n$ we substitute general term for $x_n$ in equation $1$, which yields $a_n = \frac{(nc_1 + C)^2 - c_2}{c_1}$.</p>
<p>Now, we know the value of $a_3$ as $\frac{1}{r_3}$, so we can find value of $C$ by substituting $n$ as $3$ in the general form of $a_n$. As you might note, it will give us two values for $C$ because its a quadratic in $C$, so, we take the value which gives us correct value for $a_4$ whose value we already know as $\frac{1}{r_4}$.</p>
<p>Now, our solution for a single $n$ is constant time.</p>
<h1>ALTERNATE SOLUTION:</h1>
<p>======================== </p>
<p>There is another solution using the concept of inversion of a plane. Let's see this concept in detail.
We are going to transform all points in an $x$-$y$ plane(say plane 1) to another $x$-$y$ plane(say plane 2). For each point $(x, y)$ in plane 1, we map it to $\frac{x}{r^2}, \frac{y}{r^2}$, where $r$ is distance of point $(x, y)$ from origin <em>i.e.</em> $\sqrt{x^2 + y^2}$. If we consider point $(x, y)$ in polar coordinates as $r e^{i \theta}$, then we map it to $\frac{1}{r} e^{i \theta}$ in the plane 2. Transformation from plane 2 to plane 1 is simple, we just have to apply the same transformation again for all points in plane 2.</p>
<p>Now, let's see how it affects simple figures: circle and lines. Here I am going to summarise the results, you can easily derive these results by considering equations of lines and circles(doing in polar coordinates will be easier).</p>
<ul>
<li>
<p>All the circles which pass through origin in plane 1 will be mapped to straight lines in plane 2. A circle with center at $(r, 0)$ and radius $r$ will be mapped to line $x = \frac{1}{2 r}$ in plane 2.</p>
</li>
<li>
<p>All the straight lines which do not pass through origin in the first plane will be mapped to circles which pass through origin in the second.</p>
</li>
<li>
<p>All the circles which do not pass through origin in the first plane will be mapped to some other circles in the second plane.</p>
</li>
<li>
<p>All the straight lines which pass through origin in the first plane will be mapped to the same lines in the second. Also, note that if there are two points on such a line where one point is at a distance $r_1$ from origin and another at distance $r_2$, where $r_2 \gt r_1$, then distance between them in plane 1 is $r_2 - r_1$ and distance between these points in transformed plane will be $\frac{1}{r_1} - \frac{1}{r_2}$.</p>
</li>
</ul>
<p>Now, let's see how we employe this transformation to solve our problem. First, we'll choose a suitable origin in plane 1(plane where all our circles are present). Now, we see that all circles are tangent to circles $C_1$ and $C_2$ and we remember that we can transform circles passing through origin to straight lines, so, we choose the point where $C_1$ and $C_2$ touch as the origin. Now, we also assume that their centers lie on $y$-axis at points $R_1$ and $R_2$ respectively.</p>
<p>Now if we transform the plane, then circles $C_1$ and $C_2$ will become straight lines which are parallel to each other. All the circles $C_3$, $C_4$, $C_5$ $\cdots$ will become some other circles in the transformed plane. But the fact that they all are touching $C_1$ and $C_2$ before transformation means that they all touch the two straight lines which are parallel to each other after transformation, which makes all their radii equal in the transformed plane(this radius is equal to $\frac{1}{4R_1} - \frac{1}{4R_2}$). See the following figure.</p>
<p><img height="100%" src="http://i.imgur.com/tJG1Cux.png" width="100%"></p>
<p>So, the equations of lines $C_1^{\prime}$ and $C_2^{\prime}$ are $y = \frac{1}{2 R_1}$ and $y = \frac{1}{2 R_2}$ respectively.</p>
<p>Now, to find the radius of any $n^{th}$ circle in plane 1, we first find coordinates(in plane 2) of two points on the circle and we transform these points back to plane 2 and get the distance between them as the diameter.</p>
<p>We already know the $y$-coordinate of the centre of circles $C_3^{\prime}$, $C_4^{\prime}$ and so on. We need to find their $x$ coordinate now. If we have $x$-coordinate of the center of circle $C_3^{\prime}$, then we can easily find centre of any circle and we already know the radius of circles in plane 2, so we can also find the coordinates of a point on the circumference, which we'll transform back.</p>
<p>Let's see how we find $x$-coordinate of center of $C_3^{\prime}$ in plane 2. Keep referring to image below while reading this for more clarity. We know that a line passing through origin in plane 1 remains same in plane 2, so we draw a line $Z_1$ in plane 1 passing from origin and center of circle $C_3$. Now, this line in plane represented as $Z_1^{\prime}$ will also pass through center of circle $C_3^{\prime}$ and origin of plane 2. If we know distance of center of $C_3^{\prime}$ from origin somehow, we can calculate its $x$-coordinate also, since we already have $y$-coordinate.</p>
<p>We now, try to relate distances in plane 2 with distances in plane 1. Say, the distance $d$ = distance between origin and center of $C_3^{\prime}$. So, circle $C_3^{\prime}$ cuts line $Z_1^{\prime}$ at two points, distance between these points in plane 1 must be the diameter of $C_3$ <em>i.e.</em> $2R_3$ because the same line intersects circle $C_3$ at same two points. Distance of these two points from origin in plane 2 can be written as $d - r_3^{\prime}$ and $d + r_3^{\prime}$. Now, if we transform them to plane 1 and see distance between them, we can say that:</p>
<p>$2 r_3 = \frac{1}{d - r_3^{\prime}} - \frac{1}{d + r_3^{\prime}}$</p>
<p><img height="100%" src="http://i.imgur.com/URwsTar.png" width="100%"></p>
<p>In above equation, we can find the $d$ as all other variables are known. And using value of $d$ we can find $x$-coordinate of center of $x_3^{\prime}$ $=$ $C_3^{\prime}$ as $\pm \sqrt{d^2 - y^2}$. So, center of $n^{th}$ circle will be $x_3^{\prime} + 2(n-3)R_3$ or $x_3^{\prime} - 2(n-3)R_3$, we can now check which one to use by finding radius of $C_4$ and match with given value in input.</p>
<p>Now, our problem is solved. You can do the calculations yourself to find the closed formula.</p>
<h1>COMPLEXITY:</h1>
<p>Constant per query.</p>
<h1>AUTHOR'S, TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/JULY15/Setter/NTHCIR.cpp">setter</a> <br>
<a href="http://www.codechef.com/download/Solutions/JULY15/Tester/NTHCIR.cpp">tester</a> </p>enWed, 29 Jul 2015 17:07:21 +0530Comment by adurysk on lebron's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#73445<p>No.
In the first approach, the closed form of the nth term of recurrence. I find it harder than just a simple AP :P.
If you mean in inversion, then, yes, it is n'th term of an AP, but I feel it is very tricky to choose the correct origin. :)</p>aduryskWed, 29 Jul 2015 17:07:21 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#73445Comment by lebron on lebron's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#73133<p>By "formula for 2nd subtask" you mean "sum of arithmetic progression"? :)</p>lebronSat, 18 Jul 2015 04:05:48 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#73133Answer by h1ashdr@gonhttps://discuss.codechef.com/questions/72678/nthcir-editorial/73106<p>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?</p>h1ashdr@gonThu, 16 Jul 2015 19:44:37 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/73106Answer by shivam_aithttps://discuss.codechef.com/questions/72678/nthcir-editorial/73105<p>Nice! Thanks :)</p>shivam_aitThu, 16 Jul 2015 19:44:12 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/73105Answer by likecshttps://discuss.codechef.com/questions/72678/nthcir-editorial/73085<p><a href="/users/1806/bondoc73">@bondoc</a>, 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-<a href="http://www.codechef.com/viewsolution/7391329)">http://www.codechef.com/viewsolution/7391329)</a> 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. </p>
<p>May be this helps.</p>likecsThu, 16 Jul 2015 11:25:28 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/73085Answer by AnonymousBunnyhttps://discuss.codechef.com/questions/72678/nthcir-editorial/73083<p>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. </p>AnonymousBunnyThu, 16 Jul 2015 10:22:41 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/73083Comment by apptica on ohil17yo36's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#73082<p>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.</p>appticaThu, 16 Jul 2015 10:15:18 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#73082Comment by adurysk on lebron's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#73032<p>Hey,
Was the formula for the 2nd subtask also available in google search? I hope not.</p>
<p>Every problem has a pre-requisite. If you know the concept of inversion, then you can solve this problem from scratch without using google.</p>aduryskWed, 15 Jul 2015 12:53:19 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#73032Answer by jackal02https://discuss.codechef.com/questions/72678/nthcir-editorial/73023<p>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</p>
<pre><code>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.
</code></pre>jackal02Wed, 15 Jul 2015 12:10:26 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/73023Comment by rishivikram on likecs's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72986<p>Why can we write </p>
<p>xn=xn−1+c1 as xn=nc1+C ?</p>rishivikramTue, 14 Jul 2015 21:12:46 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72986Comment by cs1120him on bondoc73's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72948<p>you have to print exactly upto 6 decimal places...</p>cs1120himTue, 14 Jul 2015 09:46:57 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72948Comment by cs1120him on cs1120him's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72928<p>Nowhere it was mentioned that the solution will be accepted within 1e-6 relative error....</p>cs1120himTue, 14 Jul 2015 00:37:36 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72928Comment by bondoc73 on bondoc73's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72927<p>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.</p>bondoc73Tue, 14 Jul 2015 00:25:10 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72927Answer by k0stiahttps://discuss.codechef.com/questions/72678/nthcir-editorial/72926<p><a href="/users/66120/vijay_cipher"><a href="/users/66120/vijay_cipher">@vijay_cipher</a></a> could you provide more details on your solution? I am struggling with this single line:</p>
<p>yl=(.25*((1.0/r4)-(1.0/r3)))-rs;</p>
<p>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?</p>
<p>Thanks.</p>k0stiaTue, 14 Jul 2015 00:11:29 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72926Comment by likecs on coolsduy's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72918<p>thanks, well explained.</p>likecsMon, 13 Jul 2015 22:58:42 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72918Comment by vijay_cipher on vijay_cipher's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72910<p>The formulas(8) and (9) will be sufficient as mentioned in the wolfram link.</p>vijay_cipherMon, 13 Jul 2015 21:48:29 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72910Answer by vijay_cipherhttps://discuss.codechef.com/questions/72678/nthcir-editorial/72907<p>it is similar to <a href="http://codeforces.com/problemset/problem/77/E">this problem</a> whose solution is <a href="http://codeforces.com/blog/entry/1773">here</a>. 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 <a href="http://mathworld.wolfram.com/Inversion.html">here.</a>.
My submission is <a href="http://www.codechef.com/viewsolution/7445907">here.</a>. It is a really cool concept.</p>vijay_cipherMon, 13 Jul 2015 21:43:27 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72907Answer by jazz0002295https://discuss.codechef.com/questions/72678/nthcir-editorial/72904<p>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</p>jazz0002295Mon, 13 Jul 2015 21:12:13 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72904Answer by lohit_97https://discuss.codechef.com/questions/72678/nthcir-editorial/72895<p>Please help me with my code. My code fails on second test file in sub task 1. :/ Thanks in Advance.
<a href="http://www.codechef.com/viewsolution/7475899">View my Code here!</a></p>lohit_97Mon, 13 Jul 2015 19:48:32 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72895Comment by atulshanbhag on atulshanbhag's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72894<p><a href="/users/27853/yash_15">@yash_15</a> i don't get you, i tried casting the sqrt function to long double, didn't work</p>atulshanbhagMon, 13 Jul 2015 19:44:55 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72894Answer by k0stiahttps://discuss.codechef.com/questions/72678/nthcir-editorial/72893<p>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 <a href="http://www.codechef.com/viewsolution/7475818">submission</a>, e.g. function solve2_editorial.</p>
<p>Maybe, someone got it accepted using solution no.2? Could you please share your code?</p>
<p>p.s. Admins, Setter code is not available! Please, fix it!</p>k0stiaMon, 13 Jul 2015 19:41:11 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72893Comment by yash_15 on cs1120him's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72888<p>the floating results must always be accepted within 1e-6 relative error.</p>yash_15Mon, 13 Jul 2015 19:25:13 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72888Comment by yash_15 on atulshanbhag's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72886<p>Precision takes a toll when you are taking square roots so many times!</p>yash_15Mon, 13 Jul 2015 19:23:00 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72886Answer by nilusilu19588https://discuss.codechef.com/questions/72678/nthcir-editorial/72884<p>Were test cases weak? I used pappus chain n got 75 . Pappus chain is a special case I guess</p>nilusilu19588Mon, 13 Jul 2015 19:14:17 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72884Answer by atulshanbhaghttps://discuss.codechef.com/questions/72678/nthcir-editorial/72881<p>please tell me why this did not pass even first sub task?</p>
<pre><code>#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;
}
</code></pre>atulshanbhagMon, 13 Jul 2015 19:05:17 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial/72881Comment by noble_mushtak on bondoc73's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72861<p>What does <code>rb(i, 4, 2000)</code> do? If it loops i from 4 to 2000, that was probably the problem because for Subtask 1, I think <code>N_i</code> could be as big as <code>3000</code>.</p>noble_mushtakMon, 13 Jul 2015 17:30:02 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72861Comment by lebron on cs1120him's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72860<p>It was funny when one of my solutions was passing ONLY second case of subtask 2 but failing other 3 :D</p>lebronMon, 13 Jul 2015 17:27:53 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72860Comment by noble_mushtak on likecs's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72858<p>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.</p>noble_mushtakMon, 13 Jul 2015 17:27:33 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72858Comment by noble_mushtak on cs1120him's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72857<p>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.</p>noble_mushtakMon, 13 Jul 2015 17:26:12 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72857Comment by noble_mushtak on lebron's answerhttps://discuss.codechef.com/questions/72678/nthcir-editorial#72856<p>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.</p>noble_mushtakMon, 13 Jul 2015 17:23:15 +0530https://discuss.codechef.com/questions/72678/nthcir-editorial#72856