PROBLEM LINK:
Author: Aravind G.
Tester: Aravind G.
Editorialist: Aravind G.
DIFFICULTY:
EASY-MEDIUM, 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 y-coordinate becomes d. Given l,d, and t, we need to calculate the y-coordinate 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 non-negative 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^2x-1 and cos3x=4cos^3x-3cosx 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^{p-1}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 1
We see,
sin2a = 2sin(a)cos(a)
sin3a = 3sin(a) - 4sin^3(a) = sin(a)(3-4sin^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 2
We 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^{p-1}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^{i-1}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[k-1]*cos(2^ix)-sinSum[k-1]*sin(x)*sin(2^ix)
Expanding sin(2^ix) as we did above, we get
cosSum[k]=cosSum[k-1]*cos(2^ix)-sinSum[k-1]*sin^2(x)*2^i*cosProduct[i-1],
where cosSum[k-1], sinSum[k-1] 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[k-1]*sin(x)*cos(2^ix)+cosSum[k-1]*2^i*sin(x)*cosProduct[i-1]
or, sinSum[k]=sinSum[k-1]*cos(2^ix)+cosSum[k-1]*2^i*cosProduct[i-1]
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 y-coordinate 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 y-coordinate 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.
