The irrational was the downer for me. I decided to stick to all cos :3
Yeah for me too,bt didnt know anything except these basic formulas
Check out my solution. Oh shit, I forgot adding links, right?
Thanks!!!
You sure its not O({log_N}^{2}) ? Because that solution got big TLE on its face.
exceeded memory to store nx
What?
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.
Well, real comedy was with me- random getting 70 points XDXD
I have represented d/l as d*modInverse(l), added that part in editorial too. Forgot to aad earlier.
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.
And
Thereās nothing bad in swallowing pride to ur code as long as ur code gets AC.
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.
I too messed up with fractions (includes creating my own fraction class) but kept getting overflow WA. only last day i took modInverse.
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.
okā¦
in poinpoly what i did was a horizontal line sweeping from left_x+1
to right_x-1 but it gave me wrong answer
https://www.codechef.com/viewsolution/17389361
probably due to wrong floor and ceil values calculationā¦
&& thanks taran for the editorial !!
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.
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 CodeChef: Practical coding for everyone in which i m using just one function and make only one call at n/2
Thank you
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
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
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.