Unofficial Editorials February Long Challenge (Part - 2)

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

1 Like

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

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

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

1 Like

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.

2 Likes

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

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

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.