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

×

BROCLK - Editorial (Non Matrix Approach) (Unofficial)

4
2

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.

This question is marked "community wiki".

asked 13 Feb, 11:58

paintbrush's gravatar image

4★paintbrush
314
accept rate: 0%

edited 14 Feb, 09:56


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: https://www.codechef.com/viewsolution/17350273

link

answered 14 Feb, 16:13

barry1928's gravatar image

4★barry1928
111
accept rate: 0%

Yes that's a much simpler approach! I came to know about it only after the contest was over ;) thanks for sharing!

(14 Feb, 17:44) paintbrush4★

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

link

answered 13 Feb, 15:53

sapfire's gravatar image

4★sapfire
412
accept rate: 0%

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

(13 Feb, 18:31) paintbrush4★
(13 Feb, 18:35) paintbrush4★

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

link

answered 13 Feb, 16:25

algmyr's gravatar image

6★algmyr
734
accept rate: 0%

That's a great approach! I will try this. Thanks for sharing :)

(14 Feb, 09:52) paintbrush4★

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

link

answered 14 Feb, 16:19

albert_012's gravatar image

2★albert_012
-15
accept rate: 0%

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

link

answered 14 Feb, 16:54

barry1928's gravatar image

4★barry1928
111
accept rate: 0%

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

link

answered 14 Feb, 17:02

albert_012's gravatar image

2★albert_012
-15
accept rate: 0%

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

link

answered 17 Feb, 19:36

aman_robotics's gravatar image

4★aman_robotics
1
accept rate: 0%

Welcome :)

(2 days ago) paintbrush4★
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,349
×1,485
×539
×221
×53
×42
×34

question asked: 13 Feb, 11:58

question was seen: 1,520 times

last updated: 2 days ago