×

# 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:

View Content

## 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{align*} \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{align*}

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: \begin{align*} (a,b)\pm(c,d)=&(a\pm c,b\pm d)\\ (a,b)\cdot(c,d)=&(a+b\sin(x))(c+d\sin(x))\\ =&ac+bd(1-\cos^2(x))+(ad+bc)\sin(x)\\ =&(ac+bd(1-\cos^2(x)),ad+bc). \end{align*}

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 $(*)$.

# AUTHOR'S AND TESTER'S SOLUTIONS:

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

# RELATED PROBLEMS:

PARSIN

SINSUMQ

This question is marked "community wiki".

7★r_64
261822
accept rate: 16%

19.1k348495534

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

(13 Feb, 00:40)
3

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.

(13 Feb, 00:42)

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

(13 Feb, 00:57)

 2 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. Link to my solution answered 13 Feb, 04:00 4★ninja_69 21●1 accept rate: 0%
 1 answered 12 Feb, 17:46 3★grab 31●1 accept rate: 0%
 1 You seriously need better editorialists. answered 13 Feb, 01:28 319●1●9 accept rate: 5% Maybe you need glasses? (13 Feb, 21:49) meooow ♦6★ Looks good enough to me. Way better than previous editorials. (13 Feb, 22:03) Maybe because you guys easily solved the problems. For a newbiew, it should be stated why do we actually need matrix-expo here. (16 Feb, 19:31)
 1 Really good problem... never used matrix exponentiation like fibonacci's anywhere else before answered 13 Feb, 01:28 164●5 accept rate: 11%
 0 Wow, I found (another) simple proof for the formula in @taran_1407's editorial! Link. answered 12 Feb, 17:50 7★r_64 261●8●22 accept rate: 16%
 0 I followed the Setter's approach, but I am still getting a TLE. Can anybody help me why this solution fails? answered 13 Feb, 00:26 4★gomu 197●4 accept rate: 5%
 0 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$. answered 13 Feb, 01:05 681●1●10 accept rate: 28% 1 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 (13 Feb, 01:31) Mine was exactly same as well (14 Feb, 15:54)
 0 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? answered 13 Feb, 03:31 1●1 accept rate: 0% 1 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%C3%A9currente_lin%C3%A9aire NB: I did not find the same explanation in English. (13 Feb, 14:19) It just follows from plain matrix multiplication. Any linear recurrence can solved in this manner using matrix exponentiation. You can find relevant tutorials on the internet. (13 Feb, 21:43) meooow ♦6★ Okay thanks for the replies. I'm actually relatively new to competitive programming and have done 0 matrix exponentiation problems so far. I think I just need to learn the topic and then get some practice with it. (17 Apr, 22:49)
 0 @r_64 halin ren how to read ur page in english answered 13 Feb, 04:15 75●6 accept rate: 0%
 0 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 link This answer is marked "community wiki". answered 13 Feb, 07:12 28●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×14,828
×764
×251
×232
×82
×44
×37