# BROCLK - Editorial

Author: Trung Nguyen
Tester: Hanlin Ren
Editorialist: Hanlin Ren

MEDIUM

### 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,t(x is unknown), calculate the y-coordinate of this endpoint after t seconds.

### QUICK EXPLANATION:

By the problem statement we have \cos(x)=d/l, and the final answer is \cos(tx)\cdot l. So we only need to compute \cos(tx). There is a formula computing \cos(nx):

\cos(nx)=2\cos(x)\cos((n-1)x)-\cos((n-2)x),

and we can use fast matrix exponentiation to compute \cos(tx) in O(\log t) time.

### EXPLANATION:

#### A note to modular arithmetic

Click to view

During the contest, a lot of people asked problems on the output section, in particular related to “modular inverse”. So let’s answer them here.

Let m,a,b be integers. a is the modular inverse of b in modulo m if (a\cdot b)\equiv 1\pmod m. For example, 8 is the modular inverse of 7 in modulo 11 since

8\times 7=56\equiv 1\pmod {11}.

We can prove that, in modulo m, a has an inverse if and only if \gcd(m,a)=1. (\gcd(7,11)=1 in above case.) To find the modulo inverse of a in modulo m, one solves the following equation

ax+my=1

by the Extended Euclidean Algorithm. Note that x,y are variables to solve; x is the modulo inverse of a. The modular inverse, if exists, is unique in modulo m. (You may say 19 is also a modular inverse of 7 in modulo 11, but 19 and 8 are equivalent.)

If m is a prime(in our problem, m=10^9+7 is a prime), then every integer 1\le a < m has a modular inverse, and let’s denote it as a^{-1}. The inverse can be computed in another way:
by Fermat’s little theorem, it’s simply (a^{m-2}\bmod m).

For a rational number \frac{p}{q}, if \gcd(q,m)=1, then it’s equivalent to p\cdot q^{-1} in modulo m. For example, \frac{2}{3}\equiv 2\cdot 3^{-1}\equiv 2\cdot 333333336\equiv 666666672\pmod {10^9+7}.

Now, in modulo m where m is a prime, we can manipulate every rational number as if it was an integer. For example, let’s compute \cos(x)=d/l and \sin^2(x)=1-\cos^2(x). The corresponding Python code is:

mod = 1000000007
cos_x = (d * pow(l, mod - 2, mod)) % mod
sqr_sin_x = (1 - cos_x * cos_x) % mod


and no manipulation of fractions is involved. Everything is just elements in \mathbb{Z}/(10^9+7)\mathbb{Z}.

(Note: \sin(x) can’t be computed even if \sin^2(x) can. This is because \sin(x) might not be rational. In this case, \sin^2(x) is a quadratic non-residue modulo 10^9+7.)

(Note 2: if you use languages such as C++, beware of overflow and underflow. For example, multiplying a and b should be written as (1ll*a*b)%mod rather than (a*b)%mod; the correct way to subtract b from a is (a-b+mod)%mod rather than (a-b)%mod. Think about the reasons yourself.)

#### Setter’s Solution

First notice that x is given by \cos(x)=d/l. To see this, consider the following figure which illustrates the problem statement: OA and OB are the position of minute hand initially and after 1 seconds, respectively. And the answer after t seconds is \cos(tx)\cdot l. Therefore, our actual task is: given \cos(x) and integer t, compute \cos(tx).

Notice the following formula:

\cos(nx)=2\cos(x)\cos((n-1)x)-\cos((n-2)x)\ \ \ (*)

that means we can write \cos(tx) in a matrix-multiplication form:

\begin{pmatrix}\cos(tx)\\\cos((t-1)x)\end{pmatrix}=\begin{pmatrix}2\cos(x)&-1\\1&0\end{pmatrix}\begin{pmatrix}\cos((t-1)x)\\\cos((t-2)x)\end{pmatrix},

and therefore

\begin{pmatrix}\cos(tx)\\\cos((t-1)x)\end{pmatrix}=\begin{pmatrix}2\cos(x)&-1\\1&0\end{pmatrix}^{t-1}\begin{pmatrix}\cos(x)\\1\end{pmatrix}.

Thus we can compute \cos(tx) by fast matrix exponentiation in O(\log t) time.

#### Tester’s Solution

Again, we’re given \cos(x) and integer t and we want to compute \cos(tx). But what if we don’t know formula (*)? We can use the following (better-known) formula:

\begin{aligned} \cos(a+b)=&\cos(a)\cos(b)-\sin(a)\sin(b)\ \ \ (1)\\ \sin(a+b)=&\sin(a)\cos(b)+\cos(a)\sin(b)\ \ \ (2) \end{aligned}

All numbers we come across will be in the form a+b\sin(x). Although we don’t know \sin(x), we can represent such a number as (a,b). Therefore we can define +,-,\times on these numbers:

We can write a recursive procedure \mathrm{Solve}(t) for computing the pair (\cos(tx),\sin(tx)).

• If t=1, we return \cos(tx)=(\cos(x),0) and \sin(tx)=(0,1);
• If t is odd, then we find (\cos((t-1)x),\sin((t-1)x)) by calling \mathrm{Solve}(t-1), and (\cos(tx),\sin(tx)) can be computed by formula (1) and (2);
• If t is even, then we call \mathrm{Solve}(\frac{t}{2}) to find (\cos(\frac{t}{2}x),\sin(\frac{t}{2}x)), and (\cos(tx),\sin(tx)) can be computed similarly.

This procedure runs in O(\log t) time since every two steps decrease t by half.

Suppose we’ve computed \cos(tx)=(a,b). b must be equal to 0 since it’s possible to represent \cos(tx) by only \cos(x) terms. Therefore \cos(tx)=a and we’re done.

## On formula (*)

How to prove formula (*)? In fact I don’t know, but one might look into this page for answer. The Chebyshev polynomial of the first kind is defined as T_0(x)=1, T_1(x)=x and T_{n+1}(x)=2xT_n(x)-T_{n-1}(x). It can be proved that T_n(\cos(x))=\cos(nx), which directly implies formula (*).

### ALTERNATIVE SOLUTION:

Please feel free to share your approach ### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

### RELATED PROBLEMS:

PARSIN

SINSUMQ

7 Likes

For formula proof:

1 Like

Wow, I found (another) simple proof for the formula in @taran_1407’s editorial! Link.

I followed the Setter’s approach, but I am still getting a TLE. Can anybody help me why this solution fails?

came up with the exact formula of author . but didn’t have prior knowledge of Mexp…
it was a very good question …

What about simply using the 2 formulas-

cos (tx)= 2*{cos}^{2}(tx/2)-1 (even t)
and cos(tx)+cos(x)=2cos((t+1)x/2)*cos((t-1)x/2) (odd t)

No need for any complex as such formula if we use these.

3 Likes

yes…
this will be much time saver and also no dealing with irrational parts.

I solved it using a function similar to modular exponentiation.
\cos tx = 2\cos^2(t/2) - 1 for even t
\cos tx = 2\cos(\lfloor t/2 \rfloor) \cos(\lceil t/2 \rceil) - \cos x for odd t

Simple recursive function with memoization passes. Though I couldn’t derive an upper bound on number distinct recursive calls. I guess its around 2 * \log t.

You seriously need better editorialists.

2 Likes

Really good problem… never used matrix exponentiation like fibonacci’s anywhere else before

1 Like

I used the exact same stuff as well XD. I mean, C’mon! All it needed was a little modification of fast exponentiation for my implementation :3

1 Like

Can someone help me understand the formula manipulation to get from the first matrix representation of the formula to the second one with the second 2x2 matrix raised to the (t-1) power?

I calculated cosnx by breaking n into a sum of powers of 2 and then calculated each power recursively using the formula cos2x=2cos^2-1. I used memoization to avoid repeating the same calculations. This required no more than log(n) operations.

To combine the powers of 2, I used the formula cos(a+b)=2cos(a)cos(b)-cos(a-b). I also used memoisation in this approach by mapping the previously calculated values of cosx otherwise it would result in TLE.

2 Likes

@r_64 halin ren how to read ur page in english

need some help!
first i found out the angle with respect to positive y axis here

double angle=acos((double)D/I)


then i found the angle with respect to y axis after t seconds as this

angle=angle*T; // the final angle

ll rem=angle/(2*pi);
angle-=rem*(2*pi); // here we got the final angle


now I found the quadrant where the final angle will lie and calculate the value of d(the final y coordinate)

the i converted d into fraction using the function

and just find the inverse and print it where i am wrong

my solution my solution for BROCLK

hey everybody,
I found the x correctly. using cos(x) = d/l;
now why does doesn’t we get the final length by cos(x*t) this can +ve or -ve depending on the quadrent.
I believe cos will take care of everything as it changes the quadrent it switched the sign of value i.e from -ve to +ve or vice versa.
Please confirm… my broken code is https://www.codechef.com/viewsolution/17355814

After finding x, and also given t, why can’t we straight away find cos(tx)?

It is written in French but I guess you should be able to understand the basic idea by reading the equation.
So look for chapter: “Suite récurrente d’ordre p” on page: https://fr.wikipedia.org/wiki/Suite_récurrente_linéaire

NB: I did not find the same explanation in English.

1 Like

you wont get ans in p/q form, even if u try to use fractions in python, you’ll have to round your cos(tx), in this case you’ll get wrong ans because precision will be different.

1 Like

@siddharthp538 why not do mod 360 or 2*PI depending whether you are using degrees or radians, and then t will be a very small value and precision will be saved right ?