@@micro_seekers As far as I understood, you asked, If it's true, that any number can be represented as the number of sums of two. The answer is Yes, you can find this powers of two greedy. Go from bigger powers of two to lower. Example: 49 = 32 + 16 + 1, or 90 = 64 + 16 + 8 + 2. Good way to do it in C++: vectorpowers; int num; cin >> num; for (int i = 30; i >= 0; i--){ if(num - (1 = 0){ num -= (1
Thanks, just realized this was the hardest leetcode question in Tree segment, helped a lot...... One small addition in the last part is that we don't need to calculate depth if we just check that node is -1 in each iteration code - for i in range(self.log): if k & (1
you are right, I also implemented it this way, but he said that he didn't want to add extra steps in the pre-calc to make this work and preferred the depth way!
this guy learned english, and computer science and how to explain things clearly and put it all on youtube for free so us dumb people can learn, what a legend
Cool lecture man. I used to think there was some sort of relation between binary search and binary lifting. Well there indeed is a relation, but not exactly. I still kinda hate how some chinese contestants use the word "binary search" and "binary lifting" interchangeably, although........I sort of understand why, especially if you into a habit of writing binary search using for loops instead of while .
There is a bigger similarity if you implement binary search by using powers of two. Say that you are searching in range [L, R]. for(int i = 19; i >= 0; i--) { int mid = L + (1
@Errichto - At 11:21 : You say "And there's this condition about parents which is also quite convenient". I don't think that's the condition you mean. The condition at 11:21 is parent[ i ] < n, which is NOT the same as : parent[ i ] < i
Thanks for the explanation really helped a lot , Now As the condition is parent[i] < n , loops order will get changed and we can avoid depth track too int[][] up; int log = 17;
public TreeAncestor(int n, int[] parent) {
up = new int[n][log]; //assuming 0 is the root node parent[0] = -1;
//setting up first ancestor for( int i = 0 ; i < n ; i++) up[i][0] = parent[i];
//setting up other ancestors for( int j = 1 ; j < log ; j++) { for( int v = 0 ; v < n ; v++) { if(up[v][j-1] == -1) up[v][j] = -1; else up[v][j] = up[ up[v][j-1] ][j-1]; } }
Thank you Errichto! I'm a new subscriber to the channel and you've really helped me a lot! Your explanations are far more better than my mentors in school. TYSM!
I think leetcode has changed the question a bit now, now it is not necessaary that parent.value < node.value what I did to solve this is find the order in which nodes appear so like using bfs and then applied the same // code class TreeAncestor { public: vector bfs(vector& arr,int i){ vector res, visited(arr.size(),0); queue q; q.push(i); while(q.empty() == false){ int len = q.size(); while(len--){ int node = q.front(); q.pop(); visited[node] = 1; //add to res res.push_back(node); for(int j: arr[node]){ if(visited[j]) continue; q.push(j); } } } return res; } int LOG = 20; vector dp; TreeAncestor(int n, vector& parent) { //make tree here vector arr(n); for(int i=1;i
We would be grateful if you would ever make a proper series, or course for competitive programming.. From medium to very advanced methods concepts to solve hard competitive programming problems...
@@Errichto That's true. Normal mortals can't do it. But someone like you can just rush through most problems, you can use your strengths to the fullest and bring value to the world that others can't. Just read a problem, state your thoughts and approach, code, next problem.
For case where we need to return "-1" : How about for every query we can calculate both Kth and (K-1)th ancestor. If they are equal we return -1 else we return Kth ancestor
I think you can't do that if k == 1. if k == 1, then we're gonna check the ancestor with distance 0 and 1. errichto's implementation itself i think it is unsuited to find the ancestor with distance 0. but if you make a if else statement, i think you can...
Hi Errichto, thank you very much for your tutorials, please consider possibility to make background of your videos little less black, for example blue dark or silver dark to make them more neural, I think that in that case watching your videos will be less stressful for the eyes, thanks
Thank you.. could you please make a video on how to code branch and bound with the example on travelling salesman problem, knapsack problem or any other example. I want to know how to find the next children of the parent and how to get the final solution
I understand that if "parent[i] < i", then you can safely compute the parent array for each V in increasing order. However on leetcode it states that "parent[i] < n", which is a different thing, no? Thanks for the video!
Oh, good catch. I've misread the condition as "parent[i] < i". Then my solution shouldn't work with the current order of for-loops and the test data is apparently weak.
you are right. I used a visited array and called another function to compute for a node if it is not visited yet. i was confused on how his code passed the test cases. now i understand that test cases were weak in the past
Video request: string algorithms (KMP, Manacher). They don't occur often on CF but do on ICPC and I would like a nice resource (there aren't any nice video resources on these topics).
The same code is giving WA in test case [4,[-1,2,3,0]], [2,3], [2,2] , [2,1] U considered the nodes to be in increasing order from top to bottom, dats why it failed when the nodes are in decreasing order..
Thanks for the wonderful lecture. But I am a bit confused about the way depth[v] and up array have been computed in the leetcode problem, it is never mentioned that parent[v] < v. If this condition is not true then result should be incorrect. Right? Or I am missing something.
Superb video Errichto, would you be interested in making some String algorithms videos? Suffix array in NlogN, Ukkonen, Manacher, Hashing(This is going to be super informative, if you include the anti-hashing test breaks that were mentioned on codeforces a few years ago when you use overflow), Suffix Trie and use cases, Compressed Trie? This will add so much more value to your already amazing channel!:) Much thanks!
For those who are wondering why this solution is getting WA now on leetcode..... Leetcode has removed the condition (parent[i] < i)... You can change your code accordingly.
Very Nice Explanation 😍. I think you calculated depth in wrong manner consider this case: ["TreeAncestor","getKthAncestor"] [[6,[-1,2,3,4,5,0]],[1,4]] depth array according to code will be [0,1,1,1,1,1] but it should be [0,5,4,3,2,1] and for node = 1, 4th ancestor should be 5 but it will give -1 as depth is wrong.
When we exchange the for loops, (where the LOG for loop is before) will work in both cases (independent of the value/order of nodes) while calculating the up vector?
Hey Errichto , What can we do ..if we have two types of quries in which one query type is we can add or delete leaf node in tree and other type return Kth ancestor !?
Hi, you mentioned since input n can be upto 50k, quadratic runtime won't work. What is the limit of input till which quadratic would work and why? Thanks!
That's why I suppose for worst case tree we will get higher order ancestors rather than getting -1 too quickly in a binary tree like tree. It is supposed like log value is the value whose 2^LogValue will provide highest possible ancestor that can exist.
I´m trying to solve a similar problem but I need to calculate the sum of a given node and a number of parents ex: node 2 and 5 parents and l have to return the sum of the values of that nodes. Any ideas of how can calculate the sum if i have the table with the k ancestros
The perfect video to find before going to bed :)
Finally I meet someone who feels the same... Even before going to bed, I can understand this guy's explanations in a short time, what a legend!
Aah, that connection when you feel the exact same way as a complete stranger on UA-cam..... The Internet did break many walls
I always tried with O(n) way....thanks for this O(logN) way.....nice explanation....👍👍
I'm a beginner at CP but still was able to understand much of this, Thank you for such an amazing explanation Erichto ❤️
Thank god...I'm trying to understand this for a week now...
I hope it doesn't take another week with my video :|
@@Errichto it will surely not....😊
@@Errichto if I want to find minimum number of numbers(power of 2) that sum upto some k. Does this approach hold?
@@micro_seekers Yes, this idea is used in LCA. If you want, you can ask something particular and I will answer you.
@@micro_seekers As far as I understood, you asked, If it's true, that any number can be represented as the number of sums of two. The answer is Yes, you can find this powers of two greedy. Go from bigger powers of two to lower.
Example: 49 = 32 + 16 + 1, or 90 = 64 + 16 + 8 + 2.
Good way to do it in C++:
vectorpowers;
int num; cin >> num;
for (int i = 30; i >= 0; i--){
if(num - (1 = 0){
num -= (1
Thanks, just realized this was the hardest leetcode question in Tree segment, helped a lot...... One small addition in the last part is that we don't need to calculate depth if we just check that node is -1 in each iteration
code -
for i in range(self.log):
if k & (1
you are right, I also implemented it this way, but he said that he didn't want to add extra steps in the pre-calc to make this work and preferred the depth way!
this guy learned english, and computer science and how to explain things clearly and put it all on youtube for free so us dumb people can learn, what a legend
Yet Again Another Life Saver Video Lecture, I will share this to my friends Thanks a lot!
Incredibly chilly vibe, good explanation... overall great video, thanks!
All this time op was like - "This is so simple".
Thanks for the explanation.
These videos are gold mines, an ultimate treasure. Loved it.
They added the test case you were talking about nodes violating the condition parent[i]
I like to add just another node (N+1) above the root and parent of (N+1) is itself. now at every query if the ancestor (N+1) return -1
Good idea! No depth needed then.
great idea 😍😍
who is here after edu 110 div 2 , thanks a lot i solved E after watching this
Thank you sir, watching your video reminds me a lot when i participated in Math Contest...
Cool lecture man.
I used to think there was some sort of relation between binary search and binary lifting. Well there indeed is a relation, but not exactly. I still kinda hate how some chinese contestants use the word "binary search" and "binary lifting" interchangeably, although........I sort of understand why, especially if you into a habit of writing binary search using for loops instead of while .
There is a bigger similarity if you implement binary search by using powers of two. Say that you are searching in range [L, R].
for(int i = 19; i >= 0; i--) { int mid = L + (1
@@Errichto I love you
@Errichto - At 11:21 : You say "And there's this condition about parents which is also quite convenient". I don't think that's the condition you mean. The condition at 11:21 is parent[ i ] < n, which is NOT the same as : parent[ i ] < i
Same doubt
@Errichto 15:38 you dont need to change any condition for log calculation, All you have to do is to change the iteration in loop from j=0;j
Thank you errichto keep doing videos about CP_topics which are hard to understand.
Best explanation of binary lifting in the internet
Thanks for the explanation really helped a lot ,
Now As the condition is parent[i] < n , loops order will get changed and we can avoid depth track too
int[][] up;
int log = 17;
public TreeAncestor(int n, int[] parent) {
up = new int[n][log];
//assuming 0 is the root node
parent[0] = -1;
//setting up first ancestor
for( int i = 0 ; i < n ; i++)
up[i][0] = parent[i];
//setting up other ancestors
for( int j = 1 ; j < log ; j++)
{
for( int v = 0 ; v < n ; v++)
{
if(up[v][j-1] == -1)
up[v][j] = -1;
else
up[v][j] = up[ up[v][j-1] ][j-1];
}
}
}
public int getKthAncestor(int node, int k) {
for(int i = 0 ; i < log ; i++)
{
if(((1
Can you please explain to me why this code only solving cases where parent[i]
Thank You So Much for this wonderful video...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
thanks for all of this insane useful thing for CP
hope you have more video in the future
Thank you Errichto! I'm a new subscriber to the channel and you've really helped me a lot! Your explanations are far more better than my mentors in school. TYSM!
I think leetcode has changed the question a bit now, now it is not necessaary that parent.value < node.value
what I did to solve this is find the order in which nodes appear so like using bfs and then applied the same
// code
class TreeAncestor {
public:
vector bfs(vector& arr,int i){
vector res, visited(arr.size(),0);
queue q;
q.push(i);
while(q.empty() == false){
int len = q.size();
while(len--){
int node = q.front();
q.pop();
visited[node] = 1;
//add to res
res.push_back(node);
for(int j: arr[node]){
if(visited[j]) continue;
q.push(j);
}
}
}
return res;
}
int LOG = 20;
vector dp;
TreeAncestor(int n, vector& parent) {
//make tree here
vector arr(n);
for(int i=1;i
Instead of all this, all you got to do is switch the loops.
Nice explanation . Binary lifting doesn't seem tough anymore :)
We would be grateful if you would ever make a proper series, or course for competitive programming..
From medium to very advanced methods concepts to solve hard competitive programming problems...
More leetcode problems pleasee. Just go crazy and solve all leetcode problems and put them into a playlist
that's a lot of videos :|
@@Errichto That's true. Normal mortals can't do it. But someone like you can just rush through most problems, you can use your strengths to the fullest and bring value to the world that others can't. Just read a problem, state your thoughts and approach, code, next problem.
@@MrDivad006 nah, rather have him do lectures like these and you can try solving all the problems with the concepts he teaches
nice explanation. as a beginner, i was able to understand easily
prefect video to show the concept of that, thank you so much!
For case where we need to return "-1" : How about for every query we can calculate both Kth and (K-1)th ancestor. If they are equal we return -1 else we return Kth ancestor
I think you can't do that if k == 1. if k == 1, then we're gonna check the ancestor with distance 0 and 1. errichto's implementation itself i think it is unsuited to find the ancestor with distance 0. but if you make a if else statement, i think you can...
Very thanks for the clear explanation. I understood it again very well. Thanks a lot, Errichto!
Superb solution. initially hard to understand
Thanks Errichto, just cz you have made the video, I gt to know a new concept I never heard about! Keep making such videos!! Helps a lot!!
Great, please bring more such videos.
Just awesome, i hv gone through whole lot of comments, and the coders here are awesome.. great place to Meetup.
powers of 2 technique is also used in BIT(Binary Indexed Tree)
Hi Errichto, thank you very much for your tutorials, please consider possibility to make background of your videos little less black, for example blue dark or silver dark to make them more neural, I think that in that case watching your videos will be less stressful for the eyes, thanks
Dark gray seems neutral enough, I think.
@@Errichto ohhh, I watched several yours videos in parallel, black background is present on your first tutorials. Good luck in Code Jam competition
Waiting for game theory related video, sir.🥺
Thank you..
could you please make a video on how to code branch and bound with the example on travelling salesman problem, knapsack problem or any other example.
I want to know how to find the next children of the parent and how to get the final solution
Thankyou..Sir,can you please make stream specifically related to mathematical background..
Finally he remembered that he has a youtube channel. Thanks a ton.
Excellent material for CP
I understand that if "parent[i] < i", then you can safely compute the parent array for each V in increasing order.
However on leetcode it states that "parent[i] < n", which is a different thing, no?
Thanks for the video!
Oh, good catch. I've misread the condition as "parent[i] < i". Then my solution shouldn't work with the current order of for-loops and the test data is apparently weak.
@@Errichto Hey, thanks I have contributed a test case to Leetcode so that this fails. Sorry but now your code also fails.
@@jahnvikumari318 Cheers for that!
@@jahnvikumari318 🥲
you are right. I used a visited array and called another function to compute for a node if it is not visited yet. i was confused on how his code passed the test cases. now i understand that test cases were weak in the past
Simply amazing, Thanks Errichto.
Beautiful explanation
Video request: string algorithms (KMP, Manacher). They don't occur often on CF but do on ICPC and I would like a nice resource (there aren't any nice video resources on these topics).
Always love your explanations, the best stuff out there.
best explanation of the world
The same code is giving WA in test case [4,[-1,2,3,0]], [2,3], [2,2] , [2,1]
U considered the nodes to be in increasing order from top to bottom, dats why it failed when the nodes are in decreasing order..
To build depth array, use dfs. Then, it will work fine.
Thanks for the awesome explanation
thank you very much for this amazing tutorial
i have a doubt can any one say that in the leetcode question they did not mention parent[i]
Thanks for the to the point explanation
Now, It's looking so easy. Thank you.
Thanks for uploading this 😊
please do this kind of videos, Thank you!
Thanks for the wonderful lecture.
But I am a bit confused about the way depth[v] and up array have been computed in the leetcode problem, it is never mentioned that parent[v] < v. If this condition is not true then result should be incorrect. Right? Or I am missing something.
Yeah, you are correct
Thank you Errichto
🙏🏻🙏🏻got a couple of new thoughts 💛
thank you for this video;
How depth[v]=depth[parent[v]]+1????
This holds if depth[parent[v]] is already computed which is not always true.
Errichto your code isn't working for this problem, you have to use the dfs method to do preprocessing.
Hi...
from ur getKthAncestor() function :
for (int j = LOG - 1; j >= 0; j--) {}
if (k >= (1 = 2, k=3-2=1
j=0, 1 >= 1, k=1-1=0
STOP
2 steps are redundant above.
Instead, why don't we write mylog(x) function, which returns floor(log2(x)), and do this :
while (k > 0) {
j = mylog(k);
node = up[node][j];
k -= 1 0, j = 4, k = 19-16=3
3 > 0, j = 1, k = 3-2=1
1 > 0, j = 0, k = 1-1=0
0 > 0 STOP
- Madhukiran
Superb video Errichto, would you be interested in making some String algorithms videos? Suffix array in NlogN, Ukkonen, Manacher, Hashing(This is going to be super informative, if you include the anti-hashing test breaks that were mentioned on codeforces a few years ago when you use overflow), Suffix Trie and use cases, Compressed Trie?
This will add so much more value to your already amazing channel!:) Much thanks!
Awesome explanation
Thanks a lot.
Extremely well presented, thanks
Add this video to the Edu playlist please
done
yo this vid came in clutch been trying to understnad this problem.
Happy Easter ❤️
What a video man..... Lovely... I really enjoyed and had fun watching it...... #LoveCoding
For those who are wondering why this solution is getting WA now on leetcode.....
Leetcode has removed the condition (parent[i] < i)...
You can change your code accordingly.
waiting for sparse table lecture
2:38 I think segment tree is divide and conquer approach ??
Yeah, in some way it is. What I meant is that segment trees and fenwick trees are often implemented for perfect powers of two.
Thanks for such good content 🙌
Very Nice Explanation 😍.
I think you calculated depth in wrong manner
consider this case:
["TreeAncestor","getKthAncestor"]
[[6,[-1,2,3,4,5,0]],[1,4]]
depth array according to code will be [0,1,1,1,1,1] but it should be [0,5,4,3,2,1]
and for node = 1, 4th ancestor should be 5 but it will give -1 as depth is wrong.
Very nicely explained 🙂
Can you please explain to me why this code only solving cases where parent[i]
Perfect, Made my day.
this code no longer works since leet code improved its test cases.. actually the problem is depth is being wrongly calculated
thanks its really clear and useful!
why could you use node that has not been calculated? I mean this part: for(int v=0; v
Thank you so much.
appreciate it! Thanks
Thanku Errichto🙃
When we exchange the for loops, (where the LOG for loop is before) will work in both cases (independent of the value/order of nodes) while calculating the up vector?
yep that'll work in both cases
Sir, May I have any advice on How and when to turn my kids to Math from your perspective ? They are 2yo, and I’m preparing now)
Thanks pls do graphs dfs and bfs.
nice job
The condition of the leetcode problem has changed. Now you will need to swap the loops. XD
Hey Errichto , What can we do
..if we have two types of quries in which one query type is we can add or delete leaf node in tree and other type return Kth ancestor !?
Easy: just compute all log(N) needed ancestors when adding a new leaf. No need to do anything when removing a leaf.
@@Errichto thanks a lot :-)
Liked the part where he gets AC but he is still busy explaining with the "same expression".
Is the github solution fine? it gives some error on one of the leetcode estcases
Though the provided solution does look correct, it doesn't pass 5 out of 15 test cases on leetcode :(
Hi, you mentioned since input n can be upto 50k, quadratic runtime won't work. What is the limit of input till which quadratic would work and why? Thanks!
if you're talking about the brute force then till n
what is software you used to present
Thanks !!
Why are you using log(n) instead of log(height of tree) in your implementation ? The n (number of nodes) must be larger than height.
Log2(n)+1 will provide the height of tree only, you can even use this condition to get you log value and it will work.
@@sudhanshukumarroy7018 Did I understand correctly that n is a height of the tree in a worst case scenario ?
That's why I suppose for worst case tree we will get higher order ancestors rather than getting -1 too quickly in a binary tree like tree.
It is supposed like log value is the value whose 2^LogValue will provide highest possible ancestor that can exist.
I´m trying to solve a similar problem but I need to calculate the sum of a given node and a number of parents ex: node 2 and 5 parents and l have to return the sum of the values of that nodes. Any ideas of how can calculate the sum if i have the table with the k ancestros
nice video