BROCLK - Editorial

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

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.


[1]


  [1]: https://www.codechef.com/viewsolution/17300590

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

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

@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

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

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

@manjuransari ok… thanks !!

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

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

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

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 ?

Hello ‘d’ is opposite side right?‘l’ is Hypotenuse right?

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

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: Suite récurrente linéaire — Wikipédia

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