PROBLEM LINK:Author: Aravind G. DIFFICULTY:EASYMEDIUM, MEDIUM PREREQUISITES:Trigonometry, Divide and conquer, Basic DP, Modular Arithmetic PROBLEM:A clock has a minute hand which goes x angle per second. The minute hand has length l and the center of clock has coordinate (0,0). Initially, the other endpoint is at coordinate (0,l), and after 1 second its ycoordinate becomes d. Given l,d, and t, we need to calculate the ycoordinate of this endpoint after t seconds. QUICK EXPLANATION:From given input, we have $cos x=d/l$ and ultimately we need to compute $cos(tx)$ to calculate the answer. We use the formulae $cos(a+b)=cos(a)cos(b)sin(a)sin(b)$, $sin(a+b)=sin(a)cos(b)+cos(a)(b)$, and we also take advantage of the fact that $sin^2(x)$ and $sin(2^x)$ are rational for all nonnegative values of x, where $cosx$ is guaranteed to be rational. EXPLANATION:Subtask 1 (5 Points)Since it is guaranteed that t<=3, we can simply hard code the formulae $cos2x=2cos^2x1$ and $cos3x=4cos^3x3cosx$ and multiply it by l to get the final answer Time Complexity: O(1) Subtask 2 (15 Points)In this subtask, it is guaranteed that $t=2^p$, where p is any nonnegative integer and $t<=10^{18}$. We simply use the formula $cos(2^px)=2cos^2(2^{p1}x)1$ and compute it from p=1 till we get the value of $cos(tx)$ Time Complexity: O(log(t)) Subtask 3 and Subtask 4(Remaining 80 Points)When t is not a power of two, we have to use the standard formula of $cos(a+b)=cos(a)cos(b)sin(a)sin(b)$. Also if t is very large, trying to compute $cos(tx)$ using this formula will give TLE. Hence, we represent t as sum of powers of 2 and calculate the cosine of the sum of those angles iteratively. For example, if t=23, we need to calculate $cos(23x)$, we simply write $cos(23x)$ as $cos(16x+4x+2x+1x)$, i.e, $cos(2^4x+2^2x+2^1x+2^0x)$ and calculate it using the $cos(a+b)$ formula. Now we only need to take care of the values of $sin(a)$ and $sin(b)$ in the above formula, which may or may not be rational. (But $sin^2x$ is always rational) Observation 1We see, $sin2a = 2sin(a)cos(a)$ $sin3a = 3sin(a)  4sin^3(a) = sin(a)(34sin^2(a))$ $sin4a= 4sinacosacos2a$ and so on. Hence we can conclude that the value of $sin(na)/sin(a)$ is always rational when cos(a) is rational and n is a nonnegative integer. Therefore, $sin(na)$ can always be written as $sina$*(some rational number). Therefore $sin(ax).sin(bx)$ is always rational when cos(x) is rational and a,b are nonnegative integers. Observation 2We see, $sin(2a) = 2sin(a)cos(a)$ $sin(4a)= 4sin(a)cos(a)cos(2a)$ $sin(8a)=8sin(a)cos(a)cos(2a)cos(4a)$ Hence we can conclude that $sin(2^px)$ can be written as $2^psin(x)cos(x)cos(2x)cos(4x)...cos(2^{p1}x)$ After representing t as sum of powers of 2, we now only need to calculate $cos(2^ax+2^bx+2^cx+...2^nx)$ where $2^ax+2^bx+2^cx+...2^nx = t$ Using the standard formulae, $cos(2^ax+2^bx+2^cx+...2^nx)=cos(2^ax)cos(2^bx+2^cx+...2^nx)sin(2^ax)sin(2^bx+2^cx+...2^nx)$ and $sin(2^ax+2^bx+2^cx+...2^nx)=sin(2^ax)cos(2^bx+2^cx+...2^nx)cos(2^ax)sin(2^bx+2^cx+...2^nx)$ If we try to calculate that recursively, we see that there are overlapping subproblems. Hence, the time complexity of recursively calculating the above values is exponential. So we use a bit of Dynamic programming in this problem and store and use the previously computed sin and cos values. We create two arrays to store these computed sin and cos values. We also create an array to store the values of $cos(x)cos(2x)cos(4x)..cos(2^{i1}x)$ (these will be used in the expansion of $sin(2^ix)$ as explained above. So we create arrays cosSum[], sinSum[] and cosProduct[]. Let cosProduct[i]=$cos(x)cos(2x)cos(4x)..cos(2^ix)$ Let cosSum[i] = $cos(2^ax+2^bx+2^cx+...2^ix)$ And, sinSum[i]= $\frac{sin(2^ax+2^bx+2^cx+...2^ix)}{sin(x)}$ (we are trying not to include the possibly irrational $sin(a)$ in our calculations at this point.) At the kth iteration we have, cosSum[k]=$cos(2^ax+2^bx+2^cx+...2^{h}x)cos(2^ix)sin(2^ax+2^bx+2^cx+...2^{h}x)sin(2^ix)$ $= cosSum[k1]*cos(2^ix)sinSum[k1]*sin(x)*sin(2^ix)$ Expanding $sin(2^ix)$ as we did above, we get cosSum[k]=$cosSum[k1]*cos(2^ix)sinSum[k1]*sin^2(x)*2^i*cosProduct[i1]$, where cosSum[k1], sinSum[k1] have been previously computed and stored. All the other terms are known to us/already calculated. Similarly, we can write $sinSum[k]*sin(x)=sinSum[k1]*sin(x)*cos(2^ix)+cosSum[k1]*2^i*sin(x)*cosProduct[i1]$ or, $sinSum[k]=sinSum[k1]*cos(2^ix)+cosSum[k1]*2^i*cosProduct[i1]$ Iterating from k=0 to n, we get what we were looking for cosSum[n] (which is the value of $cos(tx)$) Multiplying by l, we get the ycoordinate of the minute hand of Chef's clock. And above all, we do all the above calculations in fractions, and not floating point numbers. (As we need the above answer in $p/q$ form. It's better to write a Fraction struct or class for this purpose. After we get the ycoordinate in p/q form, we find the modular inverse of q and store it in variable r. You can learn more about modular inverses here. We finally print (p*r)modulo($10^9+7$) as final answer. Time Complexity per test case: O(log(n)) This is my first editorial on CodeChef Discuss. It's a lengthy editorial, as I tried to explain every detail carefully, so that everyone can understand. Any suggestions, criticism and comments are highly appreciated. If there is trouble in understanding any part of the above solution, feel free to drop a question below. AUTHOR'S SOLUTION:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Feb, 11:58

A very simple approach.. We can recursively generate the result as: if(t is even): costx = 2(cos^2(tx/2))1 else: costx = 2cos((tx+1)/2)cos((tx1)/2)  cosx And we have O(logn) complexity by using dp and storing intermediate values in the recursion. Link to my code is: https://www.codechef.com/viewsolution/17350273 answered 14 Feb, 16:13
Yes that's a much simpler approach! I came to know about it only after the contest was over ;) thanks for sharing!
(14 Feb, 17:44)

Am I missing something, but how do we calculate the angle x as a rational number? answered 13 Feb, 15:53
We do not directly use angle x in the calculations.. we always use cosx or $sin^2x$ in our calculations, and both of them are rational.. And the rest of the editorial is about how to accomplish that.. (deriving cos(tx) from cos(x) ).. And I have represented and used fractions by writing a separate fractions class for multiplying, adding, and subtracting fractions.. feel free to check out my solution for functions on fractions.. ;)
(13 Feb, 18:31)
Link to my AC solution https://www.codechef.com/viewsolution/17432212
(13 Feb, 18:35)

For my solution I created a new data type that held numbers on the form $\frac{a+b\sin(\theta)}{c}$, then I happily applied trig formulas (with memoization) to simplify my expression $$ \begin{cases} \sin(2n) &=& 2 \sin(n)\cos(n) \\ \sin(n+1) &=& \sin(n)\cos(1) + \cos(n)\sin(1) \\ \cos(2n) &=& \cos(n)\cos(n)  \sin(n)\sin(n)\\ \cos(n+1) &=& \cos(n)\cos(1)  \sin(n)\sin(1) \end{cases} $$ which happily hides the fact that we work with irrational numbers until we end up with something rational at the end. Had some trouble until I realized modding $a,b,c$ was very much needed (and by then I could have just worked with things on the form $a+b \sin(\theta)$ using modular inverses). answered 13 Feb, 16:25

We can recursively generate the result as: if(t is even): costx = 2(cos^2(tx/2))1 else: costx = cos((tx+1)/2) + cos((tx1)/2)  cosx And we have O(logn) complexity by using dp and storing intermediate values in the recursion. Link to my code is: https://www.codechef.com/viewsolution/17350273 answered 14 Feb, 16:10

A very simple approach.. We can recursively generate the result as: if(t is even): costx = 2(cos^2(tx/2))1 else: costx = cos((tx+1)/2) + cos((tx1)/2)  cosx And we have O(logn) complexity by using dp and storing intermediate values in the recursion. Link to my code is: https://www.codechef.com/viewsolution/17350273 answered 14 Feb, 16:12

@barry1928 in ur code what is the meaning of k = ((dmodInverse(l,mod))%mod+100000000mod)%mod; since we have to find mod inverse of the final y coordinate why u r calculating it in the beginnig what is the use of k here ? answered 14 Feb, 16:19

We just need to find the mod inverse related to cosx(at t=1) and recursively generate other mod inverses related to cos(tx) from it. e.g. cos(2x) = 2(cos^2(x))1 So, Modular inverse related to cos2x = (2*modular inverse related to cos^2(x)1+(large multiple of mod))%mod We take a large multiple of mod here so that the value for which we are finding remainder does not become negative. answered 14 Feb, 16:54

thanks @barry1928 .. nice solution . thanks for clearing my doubt . . answered 14 Feb, 17:02

Nice approach through trigonometry for subtask 4...Thanks for sharing:) answered 17 Feb, 19:36
