Note: In my line insert function, I should actually be checking if the deque is empty instead of it having a size > 1 since we just need to access the last line. It will still work but it might have one redundant line.
According to my understanding, for each 'j' we are finding the best 'i', so j is constant for the current part but 'i' is changing, now my doubts are the following: I didn't understand how you pick x (variable) for the equation. First of all, we are at 'j' so h_j will be constant currently and you also assumed h_j^2 is constant but in -2h_i * h_j, you said h_j is 'x' (variable). In the intercept part, which must be constant and you said that h_i^2 + dp[i] is constant. Could you explain why this: h_i^2 + dp[i] is constant and h_j as x in -2h_i.h_j?
Yes, for each "j", we are finding the best "i". For every x value, a line has some y value. Consider h_j to be the x value here. Some line will give us the best y value for this x. We consider h_j to be x here because we want to find the minimum y value we can obtain with this x value. Note that 'h_i^2 + dp[i]' (variable small 'c') is from the equation 'y = mx + c'. Capital 'C' is a fixed cost given to us as input. Consider that we are at j and we have computed dp[j]. For any index k > j, this index j will become 'i' for k. After we compute dp[j], we treat it as "i". Now, we need to insert this value into our data structure so that indices to our right can possibly use it. This value is basically some information we have - the slope and the intercept. We are treating -2h_i as the slope here (variable "m") and h_i^2 + dp[i] as the intercept (variable small "c" which is in the equation "y = mx + c"). Now the only information missing in this line is x, which when we give to the line, it will give us some y value. What we are essentially doing is, when for some j we want to compute dp[j], we plug in h_j as the x value (we query our data structure with h_j as the x value). Since the line corresponding to this x value will be the optimal line (because this is how our data structure is maintained), we receive a y value, which we set to be the answer for this j. Now, we still need to add the fixed cost capital 'C' (given as input) and 'h_j^2' to this answer which has come from the modified dp recurrence. So basically, this is what our data structure will do: 1. It has a function insert(slope, intercept) which inserts a line for us 2. It has a function query(x) which will give us the minimum y value possible for this x, where x is h_j. Side note: While in this particular problem we are querying for the minimum, the same logic applies to query for the maximum.
@@AlgorithmsConquered got it bro👍. Initially I was thinking that: you are saying h_j is x (means h_j is independent variable). Now it is clear, h_j is plugin value of x in equation of line to get the best value and Li chao is doing that.
Yeah, sorry about that. This was one of my first videos where I hadn't fully understood what levels to record at. I believe that my more recent videos have decent sound quality. Do check them out!
I don’t see what the issue is here. h_j ^2 is a constant value for every j that we can add to the answer after finding dp_j. The reason I’m writing h_j as x is because we will make a function which will give us the smallest y value for some x value.
Hey, thanks for the feedback. This was one of my first videos when I was still figuring out how to record better audio. My newer videos have much louder and better audio.
Note: In my line insert function, I should actually be checking if the deque is empty instead of it having a size > 1 since we just need to access the last line. It will still work but it might have one redundant line.
I highly request you to please make a video on divide and conquer dynamic programming.
Your videos are really very helpful.
Hey, it's been a while but the video has finally arrived! th-cam.com/video/Ec3fSWk9JOw/w-d-xo.html
Understood CHT really well from this video, thanks!
saarang orz
Could you explain the slope - y.slope - 1 at 21:35?
This video is really awesome, you made it look so simple !! Thank you!!!
Glad it was helpful!
TBH, the video is really good, lovely work :)
According to my understanding, for each 'j' we are finding the best 'i', so j is constant for the current part but 'i' is changing, now my doubts are the following:
I didn't understand how you pick x (variable) for the equation. First of all, we are at 'j' so h_j will be constant currently and you also assumed h_j^2 is constant but in -2h_i * h_j, you said h_j is 'x' (variable). In the intercept part, which must be constant and you said that h_i^2 + dp[i] is constant. Could you explain why this: h_i^2 + dp[i] is constant and h_j as x in -2h_i.h_j?
Yes, for each "j", we are finding the best "i". For every x value, a line has some y value. Consider h_j to be the x value here. Some line will give us the best y value for this x. We consider h_j to be x here because we want to find the minimum y value we can obtain with this x value.
Note that 'h_i^2 + dp[i]' (variable small 'c') is from the equation 'y = mx + c'.
Capital 'C' is a fixed cost given to us as input.
Consider that we are at j and we have computed dp[j]. For any index k > j, this index j will become 'i' for k. After we compute dp[j], we treat it as "i". Now, we need to insert this value into our data structure so that indices to our right can possibly use it. This value is basically some information we have - the slope and the intercept. We are treating -2h_i as the slope here (variable "m") and h_i^2 + dp[i] as the intercept (variable small "c" which is in the equation "y = mx + c").
Now the only information missing in this line is x, which when we give to the line, it will give us some y value. What we are essentially doing is, when for some j we want to compute dp[j], we plug in h_j as the x value (we query our data structure with h_j as the x value). Since the line corresponding to this x value will be the optimal line (because this is how our data structure is maintained), we receive a y value, which we set to be the answer for this j. Now, we still need to add the fixed cost capital 'C' (given as input) and 'h_j^2' to this answer which has come from the modified dp recurrence.
So basically, this is what our data structure will do:
1. It has a function insert(slope, intercept) which inserts a line for us
2. It has a function query(x) which will give us the minimum y value possible for this x, where x is h_j.
Side note: While in this particular problem we are querying for the minimum, the same logic applies to query for the maximum.
@@AlgorithmsConquered got it bro👍. Initially I was thinking that: you are saying h_j is x (means h_j is independent variable). Now it is clear, h_j is plugin value of x in equation of line to get the best value and Li chao is doing that.
at 7:15 it should be monotonic*
What exactly?
Kind of impossible case, but may be possible: when lines are parallel, then to check which line gives best can be checked by intercept value.
Yes, I think this problem does generate some parallel lines: cses.fi/problemset/task/2084
lines i dont think can be parralel as slopes are -2*h[j] and problem stat mentioned it that all h[i['s are strictly increasing
@@punitkumarojha817 In this particular problem we won't have parallel lines but in some other problems we can.
Please upload more videos
Thank you
I M late.... sorry bro. Btw Nice video :) .. GL
amazing video bro, btw the sound is quite small :((
Yeah, sorry about that. This was one of my first videos where I hadn't fully understood what levels to record at. I believe that my more recent videos have decent sound quality. Do check them out!
orz
Nice bedio I liek
hj is x, then hj^2 should be x^2 right?
I don't get you. Could you please elaborate?
@@AlgorithmsConquered Thanks for the reply, 3:15 you are taking "hj^2" as constant but later 3:58 taking "hj" as "x"?
I don’t see what the issue is here. h_j ^2 is a constant value for every j that we can add to the answer after finding dp_j. The reason I’m writing h_j as x is because we will make a function which will give us the smallest y value for some x value.
Got it!! Thanks
Nciec1 👍
gg
10th.
Try to speak fast and loud.
Hey, thanks for the feedback. This was one of my first videos when I was still figuring out how to record better audio. My newer videos have much louder and better audio.
@@AlgorithmsConquered Nice :)
Gg
I m late
first :)
orz
Second