Unofficial Editorials February Long Challenge (Part - 2)

editorial
, , , , ,
61

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

62

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

63

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[][]{{2*v,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 Program for Fibonacci numbers - GeeksforGeeks

64

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.

65

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

66

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

67

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

68

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

69

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

70

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 Modular multiplicative inverse - GeeksforGeeks

1 Like
71

Sorry, didnt notice! Will do right away

72

Done @taran_1407 - sorry for delay.

73

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

1 Like
74

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
1 Like
75

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 ?

76

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.

1 Like
77

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