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


Unofficial Editorials February Long Challenge (Part - 2)


Hello Guys,

This is part two of Unofficial Editorials February Challenge, containing editorials for CARPTUN, BROCLK and POINPOLY.

For other editorials, refer CHEFCHR, CHEFPTNT and PERMPAL here.

Problem : CARPTUN

Problem Difficulty: Easy

Problem Statement:

Given Delay times of N toll booths, speed of cars S, number of cars C and the distance D between each tol booth, determine the delay between First car and Last car.



Sub-task 1:

In this case, There are only two cars, so we can actually simulate the whole process in $O(CN)$ without getting TLE.

Let $time[i][j]$ denote exit time of ith car from jth toll.

For first car, Time taken by car to exit from ith toll is $time[0][i] = time[0][i-1]+D/S+A[i]$. (Taking into account the time taken to reach toll and Delay time at ith tunnel.)

For subsequent cars, Time taken by car to exit ith toll would depend upon exit time of previous car. Specifically, $time[C][i] = max(time[C][i-1]+D/S, time[C-1][i])+A[i]$

Above relationship because when we reach the toll, there might be a car already there, in which case we'll have to wait till that car completes its delay time. If there's no car when we reach there, we can start the delay time immediately.

Final Answer would be $time[C-1][N-1] - time[0][N-1]$.

Refer this solution for details.

Subtask 2:

Now, Number of cars is upto $1e6$, which means that $O(CN)$ solution will time out. We need some observations to speed up our solution to $O(N)$.


  1. Speed and Distance given in problem is irrelevant.
    Proof: Since each car has to cover $D*(N-1)$ distance to reach from first toll to last toll, all cars will have the same delay $D*(N-1)/S$ due to driving, thus, it would be better to simply ignore this delay.
  2. The Final Answer will be $max(A[i])*(C-1)$.
    Proof: Suppose a car can now move with the infinite speed. Now, the only time each car has to wait will be max(A[i]). This can be proved easily, thus left as an exercise.

Hence, we get the answer $max(A[i])*(C-1)$ in $O(N)$ time.

Link to my solution.

Link to my Code.

Problem : BROCLK

Problem Difficulty: Easy-Medium

Prerequisites: Matrix exponentation, Trigonometric identities.

Problem Statement:

Given a clock with one hand (Don't know how Chef see the time from it :P), which got broken, now move by fixed angle. We are not given this angle, but Length of hand L, and Distance of tip of hand from X-axis after one second.

We are supposed to find distance of tip of hand from x-axis.


We are given following scenario.

alt text

Time for some Math:

We can see that the triangle in figure is a right triangle. Time for Trigooonmetry.

We can see that for given position, $\sin (90 - \theta) = \cos \theta = D/L$.

We can easily see that After T seconds, The angle moved by hand is $T*x$, and thus, Our final answer would be $L*\cos(T*X)$.

Now, How to calculate $\cos(T*X)$ ??

Important property: $\cos(N*X) = 2*\cos(X)*\cos((N-1)*X) - \cos((N-2)*X)$

Proof can be found here

When T is upto $1e6$:

In this case, we can Run a loop from 1 to T aand compute the answer. Refer this.

When T is around $1e18$:

Now, we cannot run a loop as we will get TLE.

But, observe the above Recurrence Carefully. Doesn't is resemble the well know Fibonacci Sequence. So, we will calculate the Tth value of above recurrence in $O(logT)$ time, getting 100 points, in same manner as we Calculate Nth Number of Fibonacci Sequence, as explained here.

Not so easily, Because above explanation is lacking one point regarding use of Modular inverse, as well as Formation of matrix , which i have intentionally left to as to give you a chance to try even after the contest. DO GIVE A TRY BEFORE RUSHING TO SOLUTION. (This very point kept my solution hanging till the last day.)

View Content

Link to my code.

Problem : POINPOLY

Problem Difficulty: Medium

Problem Statement:

Given a convex polygon consisting of N points, Find and print $floor(N/10)$ points lying strictly inside it or report if it's impossible.


Geometry is scary, Polygon is no less. But, Triangle are our friends in this problem. Wanna know how??

See the following picture.

alt text

This way, We have divided our polygon into a set of triangles. Now, For a triangle, it is easy to determine it a point lie strictly inside the tirangle, using following property. If ABC is the riiangle and P is the point to be checked, then

Area(ABC) = Area(PAB)+ Area(PAC)+Area(PBC) And, None of these three triangle should have area 0 (P will lie on border of triangle in this case.)

Now, Coming to implementing part, How to select points to be checked??

The answer is, Process all triangles one by one and Check points around the corners of triangle (In all 8 directions) and add them to answer if they lie inside.

Now Comes the crux of Solution. Triangle is a convex polygon, thus, all points lying inside a triangle will be adjacent to each other. This means that we can continue adding points into our answer bag, until we get sufficient number of points or there aren't anymore points inside triangle, thus we will move to next triangle.

We must check surrounding 8 cells, and insert into answer bag, as well as search its neighbors (Just like moving inside a grid). Make sure not to process any point twice.

And that's all, 100 points to you because you have solved and implemented this solution.

For implementation details, refer my Code.

This brings end to part 2, Hope you liked them.

Feel free to post your queries.

Enjoy coding!!

asked 12 Feb, 17:34

taran_1407's gravatar image

accept rate: 23%

edited 13 Feb, 02:33


Part 3: Editorial of Chef and Land Labeling will be posted, if you people drop a comment below.

(12 Feb, 17:38) taran_14076★

@taran_1407 in ur second solution for <=1e6 how you deal with fraction parts.

(13 Feb, 02:00) worldunique3★

I have represented d/l as d*modInverse(l), added that part in editorial too. Forgot to aad earlier.

(13 Feb, 02:34) taran_14076★


in poinpoly what i did was a horizontal line sweeping from left_x+1

to right_x-1 but it gave me wrong answer

probably due to wrong floor and ceil values calculation...

&& thanks taran for the editorial !!

(13 Feb, 02:48) worldunique3★

Well, im not much in c++, so i cant exactly point out any bug in ur code.

And its no problem, i had the editorials written yesterday night only, but had class till 5 today, so got late in posting.

(13 Feb, 02:53) taran_14076★

@taran_1407 If possible please add the editorial for Chef and Land Labelling.

(13 Feb, 11:50) pk3013★

Well, My approach was to use O(N^3) brute force algorithm, coupled with a few observations, one being the same as official editorial. (Regarding Number of divisors)

I'll try to post if i can, but no promise.

PS: Sorry for late reply

(14 Feb, 00:08) taran_14076★
showing 5 of 7 show all


I used simple formula.

Suppose we want to calculate $cos(nx)$, then-

Even n-

Just use $cos(nx)=2{cos}^{2}(n/2)x-1$ . We know $cosx$ and hence we can find numerator and denominator in $logN$ time.

Odd n-

Notice that denominator portion for $cos(nx)$ (unreduced form-numerator and denominator not in lowest term) is nothing but ${L}^{n}$. Now we use-


The RHS of denominator is nothing but case of even $n$, which we did earlier. The only thing to do is to subtract $cos(x)$. Now, notice that $cos(x)=D/L$. I already know the final denominator, I just need to know the numerator part. Its nothing but $D* DenominatorOf(cos((n+1)/2x)*cos((n-1)/2x))$ [I think you guys guessed the denominator by now? :3 :p )



LOL this was a rollercoaster for comedy as I solved it. Initially, I was like "MEh, Geometry. GGWP I give up."

But, just for fun's sake, I decided to experiment out and submitted a $random$ solution which passed for $70$ points. Then my next few hundred submissions were spent on trying to grab those 30 points.

What I did was-

Assume large $N$. We know that since no 3 points are collinear, there must be difference of at least 1 in y coordinate for any 3 points, else $y=k$ is a line passing through them. This means, if $N$ is large, the diagonally opposite vertex is kind of "far" from the original one. So just take their mid point - it will lie inside the polygon.

Yeah, thats it, no checks on if point is inside or etc. The only thing to know is "how far" you want, or "how far" will hold good.

The principle assumptions of this approach is-

  1. The polygon is wide enough so that difference of $+-0.5$ does not affect the answer (in case the $(X_1 + X_2) or(Y1+Y2)$ is odd.
  2. The polygon is convex, not concave.

The only place it failed was a specific case for $N=10$, which was narrow. For that I had to include a check that for small polygons actually check if it lies inside or not. :/ Yeah, sad but had to swallow my pride :(


answered 12 Feb, 18:31

vijju123's gravatar image

5★vijju123 ♦♦
accept rate: 18%

edited 13 Feb, 00:52

Well, for this problem, i wrote the solution, and submitted and woah, got 100 points in one go. Frankly, i was sure my implementation was right, but i wasn't sure if my idea will work in tight bound cases.


There's nothing bad in swallowing pride to ur code as long as ur code gets AC.

(13 Feb, 02:37) taran_14076★

Broken clock alone kept me busy whole contest, than all other problems combined. So much it troubled me, that i didn't get time to explore lucas theorem for more than 10 points, when i could have got 50 because i got the same idea as editorial 2 hours before end of contest.

(13 Feb, 02:39) taran_14076★

There's nothing bad in swallowing pride to ur code as long as ur code gets AC.

Thats so lovely <33333.

roken clock alone kept me busy whole contest,

I spent 1 day trying to pass the last TC. I thought $O({Log_2}^{2}N)$ will be fine. I was so naive :(

(13 Feb, 12:53) vijju123 ♦♦5★

Yes, I even had more WAs on this problem alone than all other problems combined for this contest.

Only last day i used Modular Inverse that did the trick.

(14 Feb, 00:09) taran_14076★

Well, I had so many WAs in POINTPOLY trying to get the 30 point subtask- so many that I was afraid I will cross the 500 submission limit XD

(14 Feb, 00:21) vijju123 ♦♦5★

For POINPOLY, i got 100 points in one go.

Frankly, i try to make as less submissions as possible. Otherwise, in longs of 2017, many problems had near 50 submissions of mine, with really minor differences (never reached 100 i guess).

It's too an achievement, achieved by only a few ;)

(14 Feb, 00:26) taran_14076★

It's too an achievement, achieved by only a few ;)

True...but I still wont prefer it in Cook-offs :p :3

(14 Feb, 02:16) vijju123 ♦♦5★

Well, you won't have that much time for a problem.

and if you had, RIP your rating if the problem is out of first 3.

(15 Feb, 18:55) taran_14076★

And what if I skip first 3 and dive at 5? Still RIP :( :3 :p XD

(15 Feb, 23:25) vijju123 ♦♦5★

Well, if u skip first 3, either u r too genius if u manage AC, and then solve others.

If u didn't get AC in 5th and didn't attempt, i will take it as intentional rating drop.

PS: I posted an answer below, but couldn't get the LaTex right.., please help!!

(16 Feb, 11:27) taran_14076★
showing 5 of 10 show all

For BROCLK we can also do this, Lets say i want to calculate

cosnx ,n can be expressed in binary form, So lets say cos5x=cos(x+4x)

So just calculate cosx,cos2x,..cos(log(n)(x)). , And also calculate sinx,sin2x,sin4x,.. (Sin2n=2sinn*cosn (Keep the irrational separate)) Now solving ,


First cos3x=cosx.cos2x - sinx.sin3x

(Take care that sinx is irrational,but multiplication of two sin is rational)

Sin3x=cosxsin2x + sinxcos2x

After this calculate cos7x=cos(3x+ 4x)

My solution:


answered 13 Feb, 00:20

vivek_1998299's gravatar image

accept rate: 23%

The irrational was the downer for me. I decided to stick to all cos :3

(13 Feb, 00:45) vijju123 ♦♦5★

Yeah for me too,bt didnt know anything except these basic formulas

(13 Feb, 00:47) vivek_19982996★

Check out my solution. Oh shit, I forgot adding links, right?

(13 Feb, 00:51) vijju123 ♦♦5★


(13 Feb, 00:55) vivek_19982996★

I too messed up with fractions (includes creating my own fraction class) but kept getting overflow WA. only last day i took modInverse.

(13 Feb, 02:40) taran_14076★

For broken clock I used the formula :
cos (x+y)=2cos(x)cos(y)-cos(x-y). So when n is odd, it broke down to
cos(n/2+(n/2+1))=2cos(n/2)cos (n/2+1)-cos(1). So I was saved from matrix expo., instead just a simple recursion worked, with just saving the already computed values in a map avoiding recalculation.

My POINPOLY solution is same as yours. And yes, great editorials :)


answered 14 Feb, 00:27

kaushal101's gravatar image

accept rate: 10%

For POINPOLY , a simple technique is to find the centroid of the polygon and then simply finding the mid pts of each of the vertices and the centroid. This gave 70 pts and somehow failed for testcase 1 which turned out to be N=10 when I checked with assertions.That case had to be dealt separately.


answered 13 Feb, 03:03

abx_2109's gravatar image

accept rate: 0%

I really hated to deal with that case separately, but well, desparate times call for desparate emasures XD. And I was there thinking its just me stuck on that damn $N=10$ case. XD

(13 Feb, 13:20) vijju123 ♦♦5★

Probably that N=10 case was the trump card :P and should have been included for 70 pts case also as a lot of random techniques passed for 70 pts.

(14 Feb, 02:19) abx_21094★

They had more $N=10$ cases in the 70 point subtask. Thing is, the deadliest one wasnt the one they expected- the 30 point one turned out to be deadlier than rest.

But still, "Brute force for $N \le100$ and apply the "random technique" for other $N$ would still pass. So, its ok. 70 points turned out to be boaster for people tbh :3

(14 Feb, 10:36) vijju123 ♦♦5★

for POINPOLY : I have another observation and it worked but i don't know whether it's fully correct or not(may be the test cases are weak)?

My observation : since all the co-ordinates have integer value, so, minimum height of the polygon can be $(n - 4)/2$ . How? : since the polygon is convex so, maximum two points have same y co-ordinate and similarly in worst case the upper part(the farthest from this point) has also two points having same y co-ordinate and now since we are considering the farthest point so, we can assume that there are almost equal number of points on both side of the line(line joining the farthest point) and so, we have atleast $(n - 4)/2$ points having different y co-ordinates and at worst case their differences are '1'. so, minimum height will be $(n - 4)/2$. Now, the solution is easy as we have to find only $N/10$ (far less than ~ $N/2$ points and we know that our line lies completely inside the polygon. so, we can iterate on integer y co-ordinates and get our points. Now, the question arises what about x co-ordinate ? How do we claim that it's value is also an integer? Well, for this what i have done is I started from middle point and go on traversing in both direction one by one and i thought that this works because we are considering two farthest points and similarly we can claim that the width of the polygon at the middle is at worst $(N - 4)/2$ and hence truncating to the nearest x co-ordinate will not make the point lie outside the polygon!

If someone will find something wrong then please let me know :)


answered 13 Feb, 07:29

pk301's gravatar image

accept rate: 16%


Your conclusion that there are points for all the y-values isn't true.

Construct a polygon with vertices:

10000   11111111
20000   22222222
40009   44454444
50018   55575555
50027   55585555
30045   33383333
20045   22272222
10036   11151111
   18      20000
    9      10000
There are just 13 internal grid points, which are at

10009 11121111
10018 11131111
10027 11141111
20009 22232222
20018 22242222
20027 22252222
20036 22262222
30009 33343333
30018 33353333
30027 33363333
30036 33373333
40018 44464444
40027 44474444

(17 Feb, 06:04) john_smith_36★

why 10 , 11112 will not lie inside

this was

from geeks from geeks, i just check for for (10 ,11112) and its showing yes as output ?? why ?

(17 Feb, 06:49) worldunique3★

Read comments there. The code and procedure given at geeksforgeeks for point inside a polygon is incorrect. I know because I had to write an editorial, and that thing failed on edge cases.

(17 Feb, 10:46) vijju123 ♦♦5★

@vijju123 i have check for most points... yes this g4g code is totally wrong .. gives wrong output in most cases ..

(17 Feb, 17:48) worldunique3★

Hello Community, Here is my first effort in making a editorial, and contributing to community. Problem Link : Please do have a look :


answered 15 Feb, 13:50

ayushgupta1997's gravatar image

accept rate: 0%

Can you please look at my solution and tell why it is not passing the last subtask

on each iteration i m dividing the angle by 2 and calculate value accordingly ie O(log(time))

Thank You


answered 12 Feb, 18:02

sagar_sam's gravatar image

accept rate: 0%

You sure its not $O({log_N}^{2})$ ? Because that solution got big TLE on its face.

(13 Feb, 01:00) vijju123 ♦♦5★

it is O(log n), i m using two different function, one for calculating cos(nx) and other for calculating sin(nx) but sin(nx) use already computed value from the map

or you can look at this solution in which i m using just one function and make only one call at n/2

Thank you

(13 Feb, 11:58) sagar_sam4★

@vijju123 can you please correct me where i m wrong

Thank you

(13 Feb, 17:09) sagar_sam4★

It seems surprisingly fine to me. Can you code the same and submit in C++? To rule out any language difference in this.

(13 Feb, 18:36) vijju123 ♦♦5★

Maybe the excessive use of mod in block where t%2 != 1.

Can't be sure because I'm not versed in python.

(14 Feb, 00:11) taran_14076★
  1. How did we reduce the cos(tx)*L to p/q form? I am having some problem in understanding this part. Is it by changing for eg 0.56 to 56/100 then dividing by common gcd i.e 14/25?

  2. And we search for a formula for cos(nx) because of exceeded memory to store nx right?



answered 13 Feb, 01:22

codesniper99's gravatar image

accept rate: 8%

exceeded memory to store nx


How did we reduce the cos(tx)*L to p/q form? I am having some problem in understanding this part. Is it by changing for eg 0.56 to 56/100 then dividing by common gcd i.e 14/25?

Yes. Getting involved with decimals was all you needed to spend an eon on this problem and still be unable to crack it. Way too many round errors.

(13 Feb, 01:24) vijju123 ♦♦5★

I would recommend you to read about modular arithmetic (especially modular multiplicative inverse). If we have a rational p/q, it can also be stated as p*(1/q) and (1/q) is same as modular multiplicative inverse.

I know this will appear confusing at first sight, but first read about modular multiplicative inverse.

(13 Feb, 02:44) taran_14076★

i have tried both approach dividing into triangles and simply using whole polygon:

  1. Approach 1:simply using polygon

in simply using whole polygon approach first i checked it contain sufficient point or not by using pick's theorem then calculated maxY and minY and then start sweeping line to adjacent point on boundary of polygon and calculating all points on line by using bresenham line points generating algorithm and checking inclusion this i passed top 6 subcases passed in less time limit and got TLE for last text

  1. Approach 2:dividing whole polygon into triangle

as said in editorial i divided polygon into triangle and used triangle inclusion test not that Area test for inclusion given in editorial because i feel it will give answer true(for inside) when point is in boundary which will give wrong answer.and similarly find points inside triangle as in previous approach(rotating line point to next point)...but this give large TLE on face only top 2 test case passed.and after testing time taken by traingle inclusion i found out it is taking too much time than fast polygon inclusion text

After contest over i saw some solutions and find that this question did a comedy with me. it is not a medium problem as tags are saying(binary search...etc.) and can be bypassed easily with some text


answered 13 Feb, 01:41

abhi55's gravatar image

accept rate: 6%

edited 13 Feb, 01:52

Well, real comedy was with me- random getting 70 points XDXD

(13 Feb, 01:55) vijju123 ♦♦5★

Yes, it can be labelled as easy-medium, If you get the obersvation.

One of my friend, rather better at coding than I am, didn't even attempt this problem but solved all others (Partial in lucas, rest all 100). Only reason: He didn't get these observations (due to geometry).

That's why i labelled it medium problem.

(14 Feb, 00:13) taran_14076★

So....looks like I am the only one who made 0 observations and crashed the party with rand() XDDDD I solved this Q only because rand() got me 70 points :3

(14 Feb, 01:00) vijju123 ♦♦5★

There might be other users too, still in shadows, remaining masked unlike you. ;)

(14 Feb, 01:19) taran_14076★

remaining masked unlike you

Ironically, in real life I prefer remaining masked. I just dont like any kind of spotlight lol.

(14 Feb, 02:15) vijju123 ♦♦5★

Hard for you to remain masked, now that you are a moderator too, an active contributor.

(15 Feb, 18:56) taran_14076★

Since I am a moderator, I cannot be masked lol. Else who will people go to resolve queries? XD People will be like "And the legend says that there is some strange force- called a moderator- which looks after the forums. Unseen to the eye, nobody has ever seen or heard any of him" XDXD

(16 Feb, 13:04) vijju123 ♦♦5★
showing 5 of 7 show all

For POINPOLY I tried to find out points only on lines joining vertices because there will be N*(N-1)/2 lines so I can easily get floor[N/10] points. For finding points on lines joined by integral points, I used the slope of lines. But the problem is when I implemented this solution I got WA for only second last case. @taran_1407 it would be really helpful if you could find the bug in my code or point out a mistake in my approach (Link to my JAVA Solution). During the contest, I solved the problem by Shuffling my set of points that I had collected while traversing on lines in hope that my code is printing some wrong points not all and it got AC. Here is code with shuffling for N=11 and which got AC.


answered 13 Feb, 11:57

cis_pie's gravatar image

accept rate: 9%

edited 13 Feb, 12:04

That case also had a $N=10$. They had included some "special" figures to hack/fail many solutions. Try to use brute force if $N\le100$ and see.

(13 Feb, 13:22) vijju123 ♦♦5★

Thanks @vijju123

(13 Feb, 13:54) cis_pie5★

for CARPTUN I have used the logic of pipelining, where the process which takes longest time decides the overall time spent. so calculate the toll which takes longest time. and multiply it with (c-1) cars


answered 13 Feb, 14:14

amitguptapc's gravatar image

accept rate: 0%

For POINPOLY, I used the fact that centroid lies inside the triangle. And with PHP I proved that [n/10] distinct lattice points exists. But when implementing it I faced some issues. My first code,I couldn't find the mistake. (Can you find?, Thanks in advance) But when I rewire the code, I used long long every where instead of int, it passed. Here's my code


answered 13 Feb, 19:38

xerefic's gravatar image

accept rate: 0%

@xerefic long is required as we r storing upto 10^9 values


answered 13 Feb, 19:41

albert_012's gravatar image

accept rate: 0%

@xerefic can u make ur method more clear

what actually u did

(13 Feb, 19:42) albert_0122★

Yeah, but long is necessary only when I add more than 3 coordinates as Each coordinate is <10^9 which comes inside int. So it is sufficient to put Long long for temp1, temp2

(13 Feb, 19:44) xerefic3★

Basically, I segregated the corrdinates into 9 types depending on the values mod 3,sk that I can guarantee that the triangle formed by three points will have its centroid as a lattice point. So I used pos[x%3][y%3]=make_pair(x,y).and iterated through the vector and found the centroid.

(13 Feb, 19:49) xerefic3★

Have a look at this solution of Pointpoly problem (it's not mine)


answered 13 Feb, 20:29

shubhu1596's gravatar image

accept rate: 0%

@shubhu1596 I know this solution should not get AC but see that user is using midpoint formula of the line segment.Because there are n/2 lines, he could get n/10 points easily!

(13 Feb, 21:56) cis_pie5★

@cis_pie what about those cases in which the mid point of such chords are same, the code does not even checks for such duplicate points

(14 Feb, 00:46) shubhu15965★

@shubhu1596 Right I know he/she should hash all the points! Luck works sometimes!

(14 Feb, 21:33) cis_pie5★

Can anybody please elaborate on converting the cos(tx)L into p/q..... @vijju123 @taran_1407


answered 13 Feb, 22:44

vedantsg4's gravatar image

accept rate: 0%

See the hidden part in editorial and read about modular multiplicative inverse.

(14 Feb, 00:16) taran_14076★

Thanks! @taran_1407 got that part.(Thanks to MITOCW) But can you please tell how you formed the matrix for cos(nx), means why f[0][0] = 2v and f[0][1] = MOD-1 (why even that -1) and that return part?? func() { ... 1. F = new long[][]{{2v,MOD-1},{1,0}}; 2. M = new long[][]{{2v,MOD-1}, {1,0}}; 3. power(N-1); 4. return mod(F[0][0]v+F[0][1]); } And i am assuming that your power function works in the same manner, the power() and multiply() of method 4 of

(15 Feb, 00:08) vedantsg44★

I have posted an answer because it wouldn't fit in comment.

(15 Feb, 19:15) taran_14076★

Can anybody help me figure out what is wrong with logic I have implemented for the problem CAR-PAL TUNNEL? I am getting a text


answered 15 Feb, 13:58

ahmdnsm's gravatar image

accept rate: 0%

Matrix Exponentation

See the equation ($T(n)$ means $\cos nx$ for current problem.)

$ \begin{pmatrix} T(n) \\ T(n-1) \\ \end{pmatrix} = \begin{pmatrix} a & b\\ c & d \\ \end{pmatrix} * \begin{pmatrix} T(n-1)\\ T(n-2)\\ \end{pmatrix} $

Now, for every linear recurrence, we have to fill this matrix with suitable values of a,b,c and d So as to make $LHS = RHS$.

For current problem, our recurrence is $\cos(N∗X)=2∗cos(X)∗cos((N−1)∗X)−cos((N−2)∗X)$

The values in Transformation Matrix shall be filled so that this equation is always satisfied. Then we will find (T-1)th power of this transformation matrix $T$, then

$\begin{pmatrix}\cos nx \\ \cos (n-1)x \\\end{pmatrix} = {\begin{pmatrix} a & b\\ c & d \\ \end{pmatrix}}^{T-1}* \begin{pmatrix} cos x\\ cos 0\\ \end{pmatrix}$

This way, we get our solution to recurrence. Also, the size of transformation matrix is the number of previous values needed to calculate current value.

This was all about Matrix Exponentation in brief. You can find more about Matrix Exponentaion from following links.


answered 15 Feb, 19:16

taran_1407's gravatar image

accept rate: 23%

edited 16 Feb, 13:01

vijju123's gravatar image

5★vijju123 ♦♦

@vijju123, please help with LaTex, Matrix isn't getting right.

(15 Feb, 19:18) taran_14076★

Sorry, didnt notice! Will do right away

(16 Feb, 12:48) vijju123 ♦♦5★

Done @taran_1407 - sorry for delay.

(16 Feb, 13:02) vijju123 ♦♦5★
static long modInv(long b){
    long p = MOD-2, out = 1;
        if((p&1)==1)out = (out*b)%MOD;
        b = (b*b)%MOD;
    return out;

@taran_1407 can you explain how you take modInverse?


answered 16 Feb, 02:47

ashudeshwal's gravatar image

accept rate: 0%


Read about fermat's little theorem, which states that if p is prime, then modular inverse of x can be found as x^(p-2) modulo p.

If p is not prime, but gcd(x, p) ==1 we may use extended euclid euclid algorithm.

All methods explained here

(16 Feb, 11:32) taran_14076★
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 12 Feb, 17:34

question was seen: 3,675 times

last updated: 17 Feb, 17:48