You are not logged in. Please login at www.codechef.com to post your questions!

×

BROCLK - Editorial

7
4

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

MEDIUM

PREREQUISITES:

Trigonometry, Fast Matrix Exponentiation, Modular Inverse

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

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.

broken clock

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

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

This question is marked "community wiki".

asked 27 Jan, 14:05

r_64's gravatar image

7★r_64
261617
accept rate: 16%

edited 12 Feb, 15:15

admin's gravatar image

0★admin ♦♦
18.3k347492525

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) worldunique3★
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) vijju123 ♦5★

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

(13 Feb, 00:57) worldunique3★

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

link

answered 13 Feb, 04:00

ninja_69's gravatar image

4★ninja_69
211
accept rate: 0%

You seriously need better editorialists.

link

answered 13 Feb, 01:28

rohitthapliyal's gravatar image

4★rohitthapliyal
28619
accept rate: 6%

Maybe you need glasses?

(13 Feb, 21:49) meooow ♦6★

Looks good enough to me. Way better than previous editorials.

(13 Feb, 22:03) nilesh31055★

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) rohitthapliyal4★

Really good problem... never used matrix exponentiation like fibonacci's anywhere else before

link

answered 13 Feb, 01:28

chaitya_62's gravatar image

3★chaitya_62
1645
accept rate: 12%

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

link

answered 12 Feb, 17:50

r_64's gravatar image

7★r_64
261617
accept rate: 16%

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

link

answered 13 Feb, 00:26

gomu's gravatar image

4★gomu
1464
accept rate: 7%

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

Link: https://www.codechef.com/viewsolution/17386831

link

answered 13 Feb, 01:05

nilesh3105's gravatar image

5★nilesh3105
4079
accept rate: 21%

edited 13 Feb, 01:06

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) vijju123 ♦5★

Mine was exactly same as well

(14 Feb, 15:54) kaushal1015★

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?

link

answered 13 Feb, 03:31

apmeyer27's gravatar image

4★apmeyer27
11
accept rate: 0%

edited 13 Feb, 03:32

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) sideralis4★

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★

@r_64 halin ren how to read ur page in english

link

answered 13 Feb, 04:15

square_root_pi's gravatar image

0★square_root_pi
253
accept rate: 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

akshatsharma's gravatar image

3★akshatsharma
1
accept rate: 0%

wikified 13 Feb, 07:13

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

link

answered 13 Feb, 08:28

manii_bi's gravatar image

3★manii_bi
1
accept rate: 0%

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

link

answered 13 Feb, 13:42

aky91's gravatar image

3★aky91
1
accept rate: 0%

1

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.

(13 Feb, 16:00) siddharthp5384★

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

(13 Feb, 16:45) dollarakshay4★

Actually this happened with me during the contest, i was getting cos(60) as 0.4999999999999999 and using Fraction if u convert it in p/q form then p comes as 4503599627370495 and q comes as 9007199254740992. p*(q^-1) comes out to be 879237148. It makes a huge diff to our ans. Actually if u do mod 360 still values will be rounded. It can give us wa.

(13 Feb, 17:12) siddharthp5384★

There is no need to use matrices or trigonometry at all. In my solution, all you need to know is how to deal with complex numbers.

First, swap X and Y coords for convenience. Then, we have complex number (d/l, sqrt(1-(d/l)^2)). Note, that real part of its Nth power times l is the answer, according to properties of complex number multiplication. But its imaginary part is irrational, how do we tackle that?

Let's denote that nasty root sqrt(1-(d/l)^2) as R. Take a look at what happens when we multiplying complex numbers that looks like (a, b*R):

(a+b*R*i) * (c+d*R*i) = (a*c-b*d*R*R) + (ad+bc*R)*i = (a*c-b*d*(1-d/l)) + (ad+bc)*R*i

As we can see, field of numbers of that kind is closed under multiplication. So, all we need is to store complex number (a, b*R) as a pair of integers (a, b), write our own multiplication function, and use binpow. Code

link

answered 13 Feb, 17:39

nikitosoleil's gravatar image

4★nikitosoleil
1
accept rate: 0%

1

This is identical to the tester's solution, only interpreted as complex numbers.

(13 Feb, 21:33) meooow ♦6★

When I use the normal iterative to compute the chebyshev and fermat's little theorem for modular inverse, I get wrong answer on the first subtask.

The given test cases are computed right tho, and yes, I need something better for when t is large but could someone tell me what's wrong in this code, at least for t <= 3?

https://www.codechef.com/viewsolution/17436393

@vijju123 @r_64

link

answered 13 Feb, 21:58

spellstaker's gravatar image

3★spellstaker
1
accept rate: 0%

There is other way to solve the question. Below is my approach:

We know e^ix = cos(x) + isin(x)

=> e^inx = cos(nx) + isin(nx)

We know cos(nx) + isin(nx) = (cos(x) + isin(x))^n

After computing we would have cos(nx) = real((cos(x) + isin(x))^n)

The multiplication can can be done in logn.

Here is the code: https://www.codechef.com/viewsolution/17348197

link

answered 13 Feb, 23:13

manjuransari's gravatar image

4★manjuransari
2
accept rate: 0%

@manjuransari at one place u used the line

t_x = (xn_x)%mod - ((((y_xn_y_x)%mod)*diff)%mod)%mod;

cant we write it as t_x = [(xn_x)- ((((y_xn_y_x))*diff))]%mod;

i.e after multiplying all the values at last we are calculating mod

why using mod everytime as question clearly mentions you have to give FINAL result as ans%mod

why using mod every time will not affect our answer

link

answered 13 Feb, 23:23

albert_012's gravatar image

2★albert_012
-15
accept rate: 0%

pls someone help

(13 Feb, 23:28) albert_0122★

Can someone please tell me what is wrong with this code?? solution

link

answered 14 Feb, 01:20

pavitra_ag's gravatar image

2★pavitra_ag
4
accept rate: 0%

@albert it is possible that multiplying the two values may result in integer overflow. Hence after multiplying two values take mod, and then multiply with third value.

link

answered 14 Feb, 10:42

manjuransari's gravatar image

4★manjuransari
2
accept rate: 0%

@manjuransari ok.. thanks !!

link

answered 14 Feb, 16:22

albert_012's gravatar image

2★albert_012
-15
accept rate: 0%

i used binomial coefficients but iam getting wrong answer for some subtasks

link

answered 14 Feb, 17:35

anjan8089's gravatar image

3★anjan8089
1
accept rate: 0%

If t=1, we return cos(tx)=(cos(x),0)and sin(tx)=(0,1); Can anyone tell me why we are initializing sin(tx)=(0,1) ?

link

answered 15 Feb, 12:04

rishav007's gravatar image

4★rishav007
211
accept rate: 0%

Can anyone please explain one example of this problem along with modular inverse calculation.

link

answered 17 Feb, 14:14

getshubhk's gravatar image

3★getshubhk
1
accept rate: 0%

What is the problem if i do the following :

  1. $\theta = \arccos(d/l)$
  2. in order to find $\cos(t* \theta)$, i find the equivalent form of $t*theta$ as $(k*2*pi + x)$ and compute $\cos(x)*l$ to get the required y.

I find x as $x = t* \theta - (int)(t* \theta/ \arctan(1)*8)* \theta$

Is the problem due to floating point airthematic ?

link

answered 18 Feb, 16:00

mcjoshi05's gravatar image

3★mcjoshi05
11
accept rate: 0%

edited 18 Feb, 16:08

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×13,381
×545
×230
×225
×55
×44
×36

question asked: 27 Jan, 14:05

question was seen: 2,921 times

last updated: 18 Feb, 16:08