BROCLK - Editorial

editorial
, , , , , ,
21

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

22

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

23

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

24

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 ?

25

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

26

came up with the exact formula of author . but didn’t have prior knowledge of Mexp

it was a very good question 


27

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
28

yes

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

29

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
30

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
31

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
32

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

33

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.

34

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

1 Like
35

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.

36

Maybe you need glasses?

37

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

38

pls someone help

39

Mine was exactly same as well

40

Maybe because you guys easily solved the problems.
For a newbiew, it should be stated why do we actually need matrix-expo here.