Chef and Gordon Ramsay (CHGORAM) : Video Editorial

editorial
, ,
1

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
2

Thank you @penta_gone, please release the editorial of CSTREE as well.

2 Likes
3

Thank you @penta_gone.

1 Like
4

Finally someone made a video on a harder problem.
Do more problems from Div1.

Thanks!

3 Likes
5

I will after I return from HackWithInfy finals.

1 Like
6

Sure. Good luck for the finals.

7

This is really helpful

8

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
9

Thank you brother :slightly_smiling_face:

10

good luck :slight_smile:

11

This is the best thing, I found today :hearts:
Thanks for the efforts.

12

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

1 Like
13

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
14

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

1 Like
15

hmmm, thanks :slight_smile: lot to learn from you. Best wishes, I hope you hit 6* in Sept Long. :upside_down_face:

1 Like
16

Thanks :slight_smile: 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
17

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.

18

Yes, it will be ready in 2-3 days :slight_smile:

2 Likes
19

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
20

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