BROCLK - Editorial (Non Matrix Approach) (Unofficial)

PROBLEM LINK:

Practice
Contest

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.

6 Likes

Am I missing something, but how do we calculate the angle x as a rational number?

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

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((tx-1)/2) - cosx


And we have O(logn) complexity by using dp and storing intermediate values in the recursion.

Link to my code is:
CodeChef: Practical coding for everyone

1 Like

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

@albert_012

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.

thanks @barry1928 … nice solution .
thanks for clearing my doubt . .

Nice approach through trigonometry for subtask 4…Thanks for sharing:)

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… :wink:

Link to my AC solution CodeChef: Practical coding for everyone

That’s a great approach! I will try this. Thanks for sharing :slight_smile:

Yes that’s a much simpler approach! I came to know about it only after the contest was over :wink: thanks for sharing!

Welcome :slight_smile: