@vijju123 Please once look at my solution i have used same aproach, but there is any mistake and i am getting it partially accepted
Regarding subway,
I got 100 pts,though my solution fails in one task that my friend said ,but the idea is the same for the correct solution with just minor modification to my solution.
first we need to know that reducing the edges to atmost 3,doesnāt change the ans -why?(just try it,if u dont get it ask(u will get it anyway 
))
What i did was just stored 2 edges (correct solution stores 3 edges anyway).
Let dp[i][j][a][b] denote the maximum possible cost on the path from vertex i to 2^jth parent of i such that the path starts with the a^{th} edge of i,and ends at the b^{th} edge to j.
we can now calculate dp[i][j+1][a][b] by merging paths,i mean in order to find max cost to 2^{j+1}th parent of i,it is basically sum of max cost from i to 2^jth parent ,and 2^jth parent to 2^{j+1}th parent.
let us say i wanna calculate dp[i][j+1][0][1],
let par=2^jth parent of i,
dp[i][j+1][0][1]=max(dp[i][j][0][0]+dp[par][j][0][1]+(0th edge to j!=0th edge from j),
dp[i][j][0][1]+dp[par][j][1][1]+(1st edge to j!=1st edge from j),
dp[i][j][0][0]+dp[par][j][1][1]+(0th edge to j!=1st edge from j),
dp[i][j][0][1]+dp[par][j][0][1]+(1st edge to j!=0th edge from j),
)
edge to j means edge ending at j along the path i to 2^{j+1}th,and starting means edge starts at j along the path i to 2^{j+1}th.
Now u can easily answer the query (u,v),
calculate ans for path (u,lca(u,v)),(v,lca(u,v)) using similar strategy ,
And then merge it again taking that 0,1 cases like before.
For the correct code u probably would have to consider all cases for 3 edges.
My solution:
3 Likes
Could anyone plz provides some insights for gears problem
Regarding Tom and jerry,
the best thing to do was consider different graph and see the pattern,u could find that the ans was the maximum clique.
Though this was kinda research problem known as visible cops and robbers game.And it has a huge proof ,saying that the answer for visible cops and robberās game is (treewidth of the graph)+1,
Hereās the paper if u want to read about it,
(At page 19,it is given that ans is treewidth +1)
However finding treewidth is NPC,but since this graph is special(chordal graph),we can do something.
In this :
It is given the treewidth of chordal graph+1=maximum clique
And maximum clique of chordal graph can be easily found using perfect elimination order.
U can read it here:
My solution:
3 Likes
why didnāt u do try to submit using pypy?
my 20 pts solution submitted in pypy fetched me 50 pts
This problem can also be solved by binary search.
1 Like
Could u please explain your solution?
I didnāt expect pypy to be faster thatās why.
The reason it passed is because the slow speed of pypy has been overcompensated by the time limit increase, but that didnāt come to my mind while solving.
Also, I would have to write A LOT of pypy code from scratch having never written NTT in python before. I think my NTT in c was too slow to pass so I want to improve that first.
yeah no problem , sorry can not comment there a upvote would help 
1 Like
For EQUILIBR, why donāt we calculate the probability when one magnitude is greater than k/2 ???
I guess ik the mistakeā¦
#(a-b)%mod != a%mod - b%mod in c++ā¦
use (( a%mod - b%mod)%mod + mod)%mod
retval = (((n + 1 - i) * retval) / i) % (mod - 1);
Are you sure that this product will be completely divisible by i?
1 Like
Because even if we place all vectors ideally (in exact opposite direction to the one with magnitude greater than 1/2), we cannot obtain 0 sum.
U need mod Inverse thereā¦ as āretvalā is moduloedā¦
(8/2)%7
is not equal to
((8%7)/(2%7) )%7
advice: avoid nCr method where u need divisionā¦
Did anyone solve the GEARS problem using DSU?
If so, a detailed approach will be appreciated!
https://cp-algorithms.com/data_structures/disjoint_set_union.html#toc-tgt-11
The code given works as it is, and the explanation is pretty neat.
nCk = ( (n+1-k)/k ) * nC(k-1) hence (n+1-k)*nC(k-1) will be always divisible by k (as i think), above suppose nCk=a , (( (n+1-k)/k ) * nC(k-1)) =b then i am just doing a=b% 1e9+7 i think internal division does not matter here as i am taking modulo of final value, firstly i am calculating nCk then i am taking modulo of it. internal division does matter here ??