Hopefully you are enjoying growing your TH-cam channel Colin. I wish you nothing but the best! You are fueling my desire to consume, and also learn! Thanks!
This was such an enjoyable video. It is way past midnight, and this is the last thing I would have wanted to do, but I went through all the questions. You will hit 1M in no time, exceptional quality videos. Keep it up!
Very useful video!!! Cool example for this would be 'Maximum sum subarray' and 'Maximum product subarray'. I mean, these two seem to be almost identical problems, but one solved via greedy approach and the other via DP.
Super duper userful Colin. I starting doing something similar where I would take questions I've solved and create Anki flashcards, with the problem & techniques that I know about. My observation is that it's using divergent thinking to lay the tools you own onto a workbench and asking "if this is the right tool, how would i use it to solve the problem?" I think this workflow maps well to any discipline so why not CP?! Please make more. Thanks!!
10:41 i think u can use linear algebra, solution is s_n=a_n+b_n with a_n+1 = 2a_n+3b_n+1 = 2a_n+3b_n and (a_1,b_1) = (6,6), the problem then is transformed to matrix power, eigenvalues..., which will requires computation but reduces the problem from O(n) to O(1)
Question 10: Just use Newton's method. Let y= x. Then iteratively update y as follows (y + x/y)/2. Once y stabilizes and remains between 2 integers, pick the lower one.
Very useful video, I found out a lot about unknown before for me properties of the mentioned in the video algorithms just by pausing and digging/googling why it's true.
Question 7 can just be done with a O(1) formula: floor((sqrt(8n+1)-1)/2) Let r be the number of complete rows. The ith row has i coins (possibly excluding the last), so the complete rows have 1+2+3+...+r coins. This equals r(r+1)/2, which is at most n. r^2 + r
For anyone wondering about the formula at 7:18 it's just a combination with repetition formula. That is (k + n - 1) over n; where k is the set from where you can take the elements(a e i o u in this case, hence 5) and n is the number of elements you need. This formula counts the amount of unique n elements groups formed with the elements of the k size set. Since there is only one way to sort these groups it also counts all the sequences that we are looking for. PS I'm sorry for my broken english, but if you need some more explanation i'll try to answer. Otherwise you can look for "combination with repetition" on internet
Question 9 with combinatorics and linear algebra: (This can probably be done by hand, I'm figuring it out while typing this out) There are "essentially" two types of rows: all 3 different, or the two outer ones the same (6 actual of each type). You only need to figure out how many rows can be put after each. (by "essentially", I mean up to some group action of flipping or recoloring) Think of it this way: It's like you have a graph of 12 nodes, each representing a valid row coloring, and 2 nodes are connected if the rows can be put atop of each other. Then, a valid coloring of the grid is just a walk in the grid, and you want the number of walks. But to get that, you just need to raise the adjacency matrix of this graph to the power of n-1 (there are n rows, but n-1 steps). Then finally multiply the result from the right by the column vector all 1's. However, you can make this graph smaller by identifying nodes of the same type together, giving you a smaller graph with 2 nodes (and a 2x2 adjacency matrix), but multiple edges between them and some self-loops. Make the new adjacency matrix out of this, and raise it to n-1, but multiply by the column vector [6, 6]^T (6 for each type). I found the matrix by hand, and it's just [3, 2] [2, 2] We need to diagonalize this, then raise the diagonal matrix to n-1, multiply by the conjugating matrices and then the vector. The eigenvalues involve sqrt(17), so to avoid floating point errors, it's best to work with a formal variable for it, create a "multiply" function, and then use binary exponentiation for a faster process. EDIT: You know what? No need for the last part with the formal variable stuff. Just binary exponentiate the matrix to n-1, then multiply by [6,6]^T. And I forgot to add: Just add the entries of the resulting vector for the final answer. Equivalently, just add the entries of the final matrix, then multiply by 6.
For q5, I agree on the combinatorics intuition but can you give a quick overview as to why it's that specific function I suppose. Also for q9, there's graph coloring sections of combinatorics and I think (don't quote me on this I'm really rusty at combinatorics) a chromatic polynomial type solution might do the trick, each cell of the rectangle would a node and you would have edges between adjacent cells I believe. Also I think it was a helpful video although I'll probably have to spend time going through the leetcode questions to better understand them.
Another way to do question 8 is to have a loop that removes leaves with no apples (and thei edges, of course). Once there are no more leaves with no apples, then the answer is just double the number of edges. Note that a node with no apple might not be leaf at the start of the loop, but after removing some others, then it may become one.
For question 7, can't you solve it directly in O(1) like this: n - k(k+1)/2 = 0 k = -1/2 + sqrt(1/4 + 2n) ans = math.floor(k) Edit: sqrt(n) is O(log(n))
Being able to decide the algorithm is important. One question I have is what do you do when you don't know the algorithm, aka how to solve the problem?
This is an incredibly useful format for learning theoretical solving. Thanks for the great vid, hope to see more in the future!
you forgot to write top competitive programmer vs
in this video he is not a top competitve programmer
ILYSM, this is so cool, especially the why this video is useful parts, and the abbreviated versions! Keep making videos man, huge fan!
Hopefully you are enjoying growing your TH-cam channel Colin. I wish you nothing but the best! You are fueling my desire to consume, and also learn! Thanks!
Incredible idea.. we need more videos like this.. it's really helpful to improve fast thinking knowledge.
This was such an enjoyable video. It is way past midnight, and this is the last thing I would have wanted to do, but I went through all the questions. You will hit 1M in no time, exceptional quality videos. Keep it up!
What an awesome video concept! Thank you, and hopefully we'll see more in the future!
Very useful video!!!
Cool example for this would be 'Maximum sum subarray' and 'Maximum product subarray'. I mean, these two seem to be almost identical problems, but one solved via greedy approach and the other via DP.
Nice!
This could be a recurring thing every so often to check up on your learning.
Thanks! :)
this content is awesome! i want you to continue this style content
Super duper userful Colin. I starting doing something similar where I would take questions I've solved and create Anki flashcards, with the problem & techniques that I know about. My observation is that it's using divergent thinking to lay the tools you own onto a workbench and asking "if this is the right tool, how would i use it to solve the problem?" I think this workflow maps well to any discipline so why not CP?! Please make more. Thanks!!
Really good stuff, I love the structure of the video and the interaction makes it easier to understand the topics
10:41 i think u can use linear algebra, solution is s_n=a_n+b_n with a_n+1 = 2a_n+3b_n+1 = 2a_n+3b_n and (a_1,b_1) = (6,6), the problem then is transformed to matrix power, eigenvalues..., which will requires computation but reduces the problem from O(n) to O(1)
Cool format, great selection of problems!
Question 10: Just use Newton's method.
Let y= x. Then iteratively update y as follows (y + x/y)/2. Once y stabilizes and remains between 2 integers, pick the lower one.
Very useful video, I found out a lot about unknown before for me properties of the mentioned in the video algorithms just by pausing and digging/googling why it's true.
Question 7 can just be done with a O(1) formula:
floor((sqrt(8n+1)-1)/2)
Let r be the number of complete rows. The ith row has i coins (possibly excluding the last), so the complete rows have 1+2+3+...+r coins. This equals r(r+1)/2, which is at most n.
r^2 + r
sqrt(n) uses log n time complexity
Bro, try this question. Asked in one of the Faangs
Given an unordered array of ints. Find all quadruples (a[i], a[j], a[k], a[l]) such that i
For anyone wondering about the formula at 7:18 it's just a combination with repetition formula. That is (k + n - 1) over n; where k is the set from where you can take the elements(a e i o u in this case, hence 5) and n is the number of elements you need.
This formula counts the amount of unique n elements groups formed with the elements of the k size set. Since there is only one way to sort these groups it also counts all the sequences that we are looking for.
PS I'm sorry for my broken english, but if you need some more explanation i'll try to answer. Otherwise you can look for "combination with repetition" on internet
ty
Question 9 with combinatorics and linear algebra:
(This can probably be done by hand, I'm figuring it out while typing this out)
There are "essentially" two types of rows: all 3 different, or the two outer ones the same (6 actual of each type). You only need to figure out how many rows can be put after each. (by "essentially", I mean up to some group action of flipping or recoloring)
Think of it this way: It's like you have a graph of 12 nodes, each representing a valid row coloring, and 2 nodes are connected if the rows can be put atop of each other. Then, a valid coloring of the grid is just a walk in the grid, and you want the number of walks. But to get that, you just need to raise the adjacency matrix of this graph to the power of n-1 (there are n rows, but n-1 steps). Then finally multiply the result from the right by the column vector all 1's.
However, you can make this graph smaller by identifying nodes of the same type together, giving you a smaller graph with 2 nodes (and a 2x2 adjacency matrix), but multiple edges between them and some self-loops. Make the new adjacency matrix out of this, and raise it to n-1, but multiply by the column vector [6, 6]^T (6 for each type).
I found the matrix by hand, and it's just
[3, 2]
[2, 2]
We need to diagonalize this, then raise the diagonal matrix to n-1, multiply by the conjugating matrices and then the vector.
The eigenvalues involve sqrt(17), so to avoid floating point errors, it's best to work with a formal variable for it, create a "multiply" function, and then use binary exponentiation for a faster process.
EDIT: You know what? No need for the last part with the formal variable stuff. Just binary exponentiate the matrix to n-1, then multiply by [6,6]^T.
And I forgot to add: Just add the entries of the resulting vector for the final answer. Equivalently, just add the entries of the final matrix, then multiply by 6.
This is soo cooollll!!!. I Like this! Please please make more of these videos.
For q5, I agree on the combinatorics intuition but can you give a quick overview as to why it's that specific function I suppose. Also for q9, there's graph coloring sections of combinatorics and I think (don't quote me on this I'm really rusty at combinatorics) a chromatic polynomial type solution might do the trick, each cell of the rectangle would a node and you would have edges between adjacent cells I believe. Also I think it was a helpful video although I'll probably have to spend time going through the leetcode questions to better understand them.
1:00 ngl you got me there xd
Question 18: Kruskal/Prim's MST also works.
If you have the MST, then just delete the edge that wasn't included in the MST.
Love this video, thank you Colin!
I have a doubt for Q17 16:30 , shouldn't we output the longest path to make sure that every node receives the message?
We find the shortest path from start node to each of the nodes. Then, we return the longest of the shortest paths.
More vids like this, do a sequel, really enjoyed it
Why did you actually pause the video in the intro😭 i thought my phone broke. i love this channel
Thank you much for this, Colin. Also, part two, when? ;)
do you know of any other videos / resources like this (guess the algorithm ) out there? I find it very helpful
Another way to do question 8 is to have a loop that removes leaves with no apples (and thei edges, of course).
Once there are no more leaves with no apples, then the answer is just double the number of edges.
Note that a node with no apple might not be leaf at the start of the loop, but after removing some others, then it may become one.
what if the solution has to be strictly below O(n) ?
For question 7, can't you solve it directly in O(1) like this:
n - k(k+1)/2 = 0
k = -1/2 + sqrt(1/4 + 2n)
ans = math.floor(k)
Edit: sqrt(n) is O(log(n))
for question 7 you can use math.
The fornula is floor(sqrt(n*2+0.25)-0.5)
This is awesome !
for Q18, couldnt you just remove one of the edges of the vertex with entrance degree = 2?
Hey, Colin. Can you solve the recent CodeChef Starter problems? Some of them are very hard and I would like a different mind to attempt it. Thanks
Hi Galen, Leetcode contest editorials when?
Being able to decide the algorithm is important. One question I have is what do you do when you don't know the algorithm, aka how to solve the problem?
we can use DSU on Q4 right ?? but I guess it will complicate the solution
For q3, we obviously have to sort it first right?
love your vids
what a great video thank you
Thanks colin
Linear Programming for most optimization problems!
is is worth studing thies algorithm in deatil?
Can you please do beginner's tutorial for soft soft mobile....please...
do you think that I should worry about not getting the solution for most of the leetcode questions?
No.
God bless you
couldnt you use dijkstras at Q14?
the cost of an edge from V1 to V2 is max(0, V2 - dist[V1]). just run the normal algo using this function to calculate the cost. pretty much it
Cfbr
Score: 11/25
Bro kindly do leetcode 862
made more such videos
Yo just hit me that hard that, please, lemme go for crying. Brb.
It took 3 minutes and 24 seconds to video to start...
algorithm
i am a cheater , i solve many of these problems so i know the answer before try to think
Brains
Answer to all questions was Brute Force. Noobs
First!!!
Hey Colin can you gift me your brain 🧠 please 🙏
Are you boy or Girl?
If you want larger audience you can start teaching ds and algo at youtube.
Dude cut your hair no offense did you dad never like make fun of you for it
rofllll..
I vote that he keeps his hair long.