Difficulty : Easy-Medium
Prerequisites : Segment-Tree , DFS , Basic Tree knowledge (Like subtree and all)
Since the video got too big i needed to divide the video into two parts
CHGORAM Part 1
CHGORAM Part 2
(I have tried my best to explain , if you find any improvement that i could make next time please let me know.)
If you find this video helpful please help our channel to grow by subscribing and sharing it with others.
Thank you.
13 Likes
Thank you @penta_gone, please release the editorial of CSTREE as well.
2 Likes
Finally someone made a video on a harder problem.
Do more problems from Div1.
Thanks!
3 Likes
I will after I return from HackWithInfy finals.
1 Like
Sure. Good luck for the finals.
I had the same idea but had hard time implementing it ( I was late to the contest and was preoccupied). Anyways good editorial and try to speak with breaks between sentences and without breaking between words
1 Like
This is the best thing, I found today
Thanks for the efforts.
For CSTREE, take adjoint of the matrix, multiply it with the matrix which consists of all 1’s, then, multiply it with the adjoint matrix again, and also multiply with (det)^k-2, tadaa! Answer is ready
1 Like
Oh! Glad to see you back. Welcome. Thank you. And one question, how did you discover it during the contest that this question can be solved by this approach? Did you solve similar questions in the past, or it was during the contest that the approach struck you?
1 Like
Nopes. See creating a matrix for spanning tree problem is known to everybody.
So I made the matrix!
(Everybody can do this!)
Now , the matrix is very special, as many numbers keep repeating every time(there is a strict pattern) , so I searched for a theorem which solves the co-factor of a big matrix of size (10^8 cross 10^8) on internet. I applied that theorem, got the answer CALCULATIONS I DID WERE OF 10 PAGES ON THE MATRIX. I suspect last problem of div-1 to be easier than this if one likes heavy-light-D
1 Like
hmmm, thanks lot to learn from you. Best wishes, I hope you hit 6* in Sept Long.
1 Like
Thanks But I am not much into ratings these days. 1-star is also Ok for me. Just solving problems is a nice experience in boring mundane life. Ratings are just for motivation I guess…
2 Likes
BTW, Karan would you mind writing a detailed editorial for CSTREE(so beginners like me can follow). This would be a great help as the official editorials may take some more time.
Yes, it will be ready in 2-3 days
2 Likes
link, i used faddev-leverrier algorithm to find adjoint in n^4, how do u manage to find adjoint in contest, i used matrix template also implemented of my of my own, but still was not getting a*adj(a)=I.det(a), could you share your adjoint code.
1 Like
I used a very smart trick. I only calculated first row of adjoint matrix…and for all the further calculations, I only calculated 1st row which solves the problem in very less time😎
1 Like