You can solve this problem in more simple manner, like we do all other partitioning problems. Check the problem on word partitioning and then try to apply the same logic here. This solution is over complicated.
Your explanation of the dp is terrible. Very poorly explained. Your explanation of how to calculate the 2d array is clear, but I have no idea what you are doing to calculate the 2 1d arrays. Okay, I understand. The results array is the index of the last word + 1!
Tushar sir your programming videos have helped me a lot. Just one point to mention is that please give the recursive relation so that we can get completely connected with the solution. Thanks!
Please try to give logical reasoning for taking any decision, like you started from left or can we club both the matrix into one but sol will become O n4 like that, will be really helpful
+Tushar, Thanks a lot for this video. I understood the solution but I did not get how you came up with thought of using dynamic programming in first place. What was your thought process ?
Hey, Filling the first 2D array which contains the values of the squared left-over length of a line is N^2. This is for large texts with like 30.000 words a problem. Wouldn't it be possible to save it in N*L? If so, how?
True, It is diappointing but it is one of the best explanation we have so far. Tushar, It would be much better if transition between the statements would be smoother. It saves a lot time on preparation as you cannot remember everything but the basic concepts.
Here's the coded solution: long solveBalancedLineBreaks(std::vector words, int limit) { std::vector cost(words.size(), std::vector(words.size(), std::numeric_limits::max())); for (size_t i = 0; i < words.size(); i++) { int sum = 0; for (size_t j = i; j < words.size(); j++) { // calculate: sum{i, j} |word]i]| sum += words[j].size(); if (j != i && sum limit) break; else { int value = (limit - sum); cost[i][j] = value * value; } } } std::vector mincost(words.size(), std::numeric_limits::max()); int i = words.size() - 1, j; while (i >= 0) { j = words.size() - 1; while (j >= i) { if (cost[i][j] < std::numeric_limits::max()) { int subcost = cost[i][j]; if (j + 1
So that the big individual spaces get more value than several smaller spaces. The same is done in TeX (en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness).
For people starting out in DP, please dont follow tushar's tutorials. His videos jumps straight into a well known solution. HIS VIDEOS DONT TEACH YOU HOW TO THINK. For dp it is very imp to come up with a recurance relation and identity the optimal substructure and overlapping subproblems. That is the base of your solution. Once you reach that, you can convert your soln to a top up approach. Watch the MIT lectures instead.
+Sandip M. Waghmare : Actually it just means that if there is 5th indexed word then it would be in next line. You can easily understand it's concept by looking at other indexes as shown in the video. Hope that helps a bit.
Sir, your code for this question is wrong..try using following case. "aaa","12345","1234567","1234","123","1234", "1", "12345","12345678","12345". take width as 12.
You have some great videos but this one didn't do a great job of explaining the reason behind the solution as much as it explained the methodology behind arriving at said solution. The matrix and the two arrays could have been better elaborated upon
I don't like how you jumped right into approaches before explaining the problem fully, like what's a space? (We learn afterward that it's whatever is left over by words)
I think we can get the solution using 1d arrays instead of 2d array. The 1d array F[i] will still represent the cost of fitting all prev words including i We will use another 1D array Acc[i] to store the accumulated sum of word lengths up till i Acc[i] = sum(F[i] ... F[0]) which will help get the sum of any interval in constant time. Now the recursive formula will be F[i]= minimum of previous F[j-1] + the error introduced of putting words j..i in a new line F[i] = min( F[j-1] + (width - (Acc[i]-Acc[j-1]) + (i-j))^2) for j= i to 0 or until (Acc[i]-Acc[j-1]) + (i-j))^2 becomes larger then width
Thank you so much, Tushar. Your videos are really helpful. I understood the procedure you have explained in this video. Can you tell me where exactly you have an explanation for the code for the Text Justification Dynamic Programming Problem?
I see many people explaining this question with minimizing badness. But how is it any better than just iterating through the list of words, and reinitializing the every time I find the last word based on word length count and separating sentences?
In you video you missed out the traversal from 2 to 3 (excluding 3). I get that we have used the word at index 2 but is there a way to fix that such that we don't get this kind of repetition?
It would help if you could also prove correctness of the algorithm. And, why should one choose a particular algorithm over another, inorder to solve a given problem.
Excellent Explanation of the most of the problems. Helped a lot in understanding dynamic programming. Can you recommend any good book for reading and subtle explanation of dynamic programming problems
In you video you missed out the traversal from 2 to 3 (excluding 3). I get that we have used the word at index 2 but is there a way to fix that such that we don't get this kind of repetition?
Super work, but you could have used the same cost matrix since its simpler. You set infinity immediately while you could have chosen to check the minimum of infinity and all other possibilities. T[i][j] = min ( "infinity" if total length > width otherwise "computed cost", min(T[i][k]+T[k+1][j])) I tried it and got the same result. We can set the start of new lines by just adding the index in the matrix as you did in previous videos to find the arrangement.
Hello, thanks for the nice video. I have the task to output a .txt file in c++ compiler with a justified width of 25 inputted by the user. I have to use ofstream and ifstream to read character by character and output each line so that the maximum number of character in a line is not more than 25. (not more than 25 characters) I need to solve this task urgently... :-( Could you please help me out?
Thanks for the explanation, but when looking at the code I don't get it. In the video, you start doing the "where to break" analysis once you hit infinity between i and j. However, in the code, you just 'continue;'. How does this work? Where does this analysis take place in the code? Thanks!
3:30 how can you tell that arrangement 2 is better then 1 only because the sqaure of empty spaces is greate? and why we should count the square, because after all number of empty spaces matter not square
This problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
At 6:17, Am I the only one who laughed when he corrected himself, and be like 10 - 2 is 4...oops no 10 - 2 is 2 and 2 squared is 4. watching at 1.5x makes it more funny! ;)
Tushar, how would we solve if we got question saying, do not consider last row penalisation, that is wheneve is in last row at as long as it fits size lets sayy 10, it wont get penalised.
Hey Maxwell, This problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
Thanks a lot. As an extension of this i have one question. Given width and number of rows, how many times you can fit in that sentence? Next sentence can start after a space from last word. It will be helpful if you share the technique. Once again thank you.
It starts from the lowest subproblem and moves to the highest problem, that's why. This problem has been explained beautifully in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
Hi, no worries - this problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
awesome job tushar!! have to say yours is the best tool for learning dynammic programming I have across simple and efficient at the same time! keep up the good work man! you are helping out so many people like me, thanks for that!
![NOSFERATU - Official Trailer [HD] - Only In Theaters December 25](http://i.ytimg.com/vi/nulvWqYUM8k/mqdefault.jpg)
![Burst Balloon Dynamic Programming[Leetcode]](/img/1.gif)
Dont really understand the explanation from minute 7:20 onwards. :(
Acc to Tushar-->Dynamic programing ==filling the table. No intutuion ,no logic, just fill the table
How the hell would anyone think of this in an interview?
Thats what I was thinking while watching the video, then decided to go with greedy algorithm :P
It has a simple solution also. You can solve it like matrix chain multiplication. Problem - 3
@@PrathamMantri I did the same
You can solve this problem in more simple manner, like we do all other partitioning problems. Check the problem on word partitioning and then try to apply the same logic here. This solution is over complicated.
thats why not everyone is a google, apple engineer
Your explanation of the dp is terrible. Very poorly explained.
Your explanation of how to calculate the 2d array is clear, but I have no idea what you are doing to calculate the 2 1d arrays.
Okay, I understand. The results array is the index of the last word + 1!
Tushar sir your programming videos have helped me a lot. Just one point to mention is that please give the recursive relation so that we can get completely connected with the solution. Thanks!
agree
Agreed
Please try to give logical reasoning for taking any decision, like you started from left or can we club both the matrix into one but sol will become O n4 like that, will be really helpful
You rock man. You rock !
+Tushar, Thanks a lot for this video. I understood the solution but I did not get how you came up with thought of using dynamic programming in first place. What was your thought process ?
Hey,
Filling the first 2D array which contains the values of the squared left-over length of a line is N^2. This is for large texts with like 30.000 words a problem.
Wouldn't it be possible to save it in N*L? If so, how?
NO explanation at all on why we are doing what we are doing. Really disappointed.
True, It is diappointing but it is one of the best explanation we have so far.
Tushar, It would be much better if transition between the statements would be smoother.
It saves a lot time on preparation as you cannot remember everything but the basic concepts.
Yes, we'll use Dynamic Programming.
:D :D
lamo
Here's the coded solution:
long solveBalancedLineBreaks(std::vector words, int limit)
{
std::vector cost(words.size(), std::vector(words.size(), std::numeric_limits::max()));
for (size_t i = 0; i < words.size(); i++)
{
int sum = 0;
for (size_t j = i; j < words.size(); j++)
{
// calculate: sum{i, j} |word]i]|
sum += words[j].size();
if (j != i && sum limit)
break;
else
{
int value = (limit - sum);
cost[i][j] = value * value;
}
}
}
std::vector mincost(words.size(), std::numeric_limits::max());
int i = words.size() - 1, j;
while (i >= 0)
{
j = words.size() - 1;
while (j >= i)
{
if (cost[i][j] < std::numeric_limits::max())
{
int subcost = cost[i][j];
if (j + 1
why do you square the number of white spaces?
So that the big individual spaces get more value than several smaller spaces. The same is done in TeX (en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness).
Yes, TeX actually uses (width - used)^3. The ^3 is to amplify discouraging unused spaces.
lame
For people starting out in DP, please dont follow tushar's tutorials. His videos jumps straight into a well known solution. HIS VIDEOS DONT TEACH YOU HOW TO THINK. For dp it is very imp to come up with a recurance relation and identity the optimal substructure and overlapping subproblems. That is the base of your solution. Once you reach that, you can convert your soln to a top up approach. Watch the MIT lectures instead.
at 7:56 .. can anyone please explain why 5 is assinged at last index in second array
??starting from 4 till 5 .. i dont get it where is 5th index
+Sandip M. Waghmare : Actually it just means that if there is 5th indexed word then it would be in next line. You can easily understand it's concept by looking at other indexes as shown in the video.
Hope that helps a bit.
I LOVE YOU !
Sir, your code for this question is wrong..try using following case.
"aaa","12345","1234567","1234","123","1234", "1", "12345","12345678","12345".
take width as 12.
You have some great videos but this one didn't do a great job of explaining the reason behind the solution as much as it explained the methodology behind arriving at said solution. The matrix and the two arrays could have been better elaborated upon
ruclips.net/video/ENyox7kNKeY/видео.html
I don't like how you jumped right into approaches before explaining the problem fully, like what's a space? (We learn afterward that it's whatever is left over by words)
What is that 5x5 matrix about? What’s the value of x and y axis? I don’t get it, it’s not explained.
I think we can get the solution using 1d arrays instead of 2d array.
The 1d array F[i] will still represent the cost of fitting all prev words including i
We will use another 1D array Acc[i] to store the accumulated sum of word lengths up till i
Acc[i] = sum(F[i] ... F[0]) which will help get the sum of any interval in constant time.
Now the recursive formula will be F[i]= minimum of previous F[j-1] + the error introduced of putting words j..i in a new line
F[i] = min( F[j-1] + (width - (Acc[i]-Acc[j-1]) + (i-j))^2)
for j= i to 0 or until (Acc[i]-Acc[j-1]) + (i-j))^2 becomes larger then width
Not at all helpful you are just telling how to solve not telling why we go ahead with Dp with this solution
For anyone interested in why Tushar went for square: ruclips.net/video/ENyox7kNKeY/видео.html
Here I come again after 9 months for this same question, History connects us lol
Ugh I dont even feel like wrapping my head around this.
No body should be asking these types of questions during a Interview and expect this answer. You won't be able to judge a person by this question.
This was little complicated!!! but finally understood :P Thanks!
You have given a very efficient solution :bestofluck
This is the only satisfactory video in RUclips till now thanks a lot for that
but what if one line can store more than 2 words?
Thank you so much, Tushar. Your videos are really helpful. I understood the procedure you have explained in this video. Can you tell me where exactly you have an explanation for the code for the Text Justification Dynamic Programming Problem?
Pet peeve: Wrong pronunciation of "infinite".
can you please share git repo link again
how will we solve covid crisis?
Roy : Yes, we will use dynamic programming for this
could anyone explain why 0-3 is INF? 0 Tushar 3 to 6+3+1 = 10 isn't supposed it be 0 ?
Thanks Bro.
I see many people explaining this question with minimizing badness. But how is it any better than just iterating through the list of words, and reinitializing the every time I find the last word based on word length count and separating sentences?
Can you please write the actual recursion!!!
Amazing explanation for this question on youtube so far. Thankyou..
his language is poor and sad
In 11:09. Why did you write 49+34? The best of 2 to the end of line is 9. Or I didn't understand
Why are we using sum of squares(spaces) for cost determination?
How J2 = 49 + 34 ?
why not J2 = 49 + 9 ?
I didn't get at 10:57 .. can anyone explain it?
In you video you missed out the traversal from 2 to 3 (excluding 3). I get that we have used the word at index 2 but is there a way to fix that such that we don't get this kind of repetition?
It would help if you could also prove correctness of the algorithm. And, why should one choose a particular algorithm over another, inorder to solve a given problem.
Excellent Explanation of the most of the problems. Helped a lot in understanding dynamic programming. Can you recommend any good book for reading and subtle explanation of dynamic programming problems
For 4 to 4 the penalty should be zero, because it's the last line.
If you don't believe me check out wikipedia on line wrap, and word wrap.
In you video you missed out the traversal from 2 to 3 (excluding 3). I get that we have used the word at index 2 but is there a way to fix that such that we don't get this kind of repetition?
Super work, but you could have used the same cost matrix since its simpler. You set infinity immediately while you could have chosen to check the minimum of infinity and all other possibilities.
T[i][j] = min ( "infinity" if total length > width otherwise "computed cost", min(T[i][k]+T[k+1][j]))
I tried it and got the same result. We can set the start of new lines by just adding the index in the matrix as you did in previous videos to find the arrangement.
Hello, thanks for the nice video.
I have the task to output a .txt file in c++ compiler with a justified width of 25 inputted by the user.
I have to use ofstream and ifstream to read character by character and output each line so that
the maximum number of character in a line is not more than 25. (not more than 25 characters)
I need to solve this task urgently... :-(
Could you please help me out?
Thanks for the explanation, but when looking at the code I don't get it.
In the video, you start doing the "where to break" analysis once you hit infinity between i and j.
However, in the code, you just 'continue;'. How does this work? Where does this analysis take place in the code?
Thanks!
Hey Tushar please upload vedio for Box Stacking problem too. please
3:30 how can you tell that arrangement 2 is better then 1 only because the sqaure of empty spaces is greate?
and why we should count the square, because after all number of empty spaces matter not square
This problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
Tushar Sir there is a O(nlogn) method for longest increasing susequence . Can this question be done in O(nlogn) also?
At 6:17, Am I the only one who laughed when he corrected himself, and be like 10 - 2 is 4...oops no 10 - 2 is 2 and 2 squared is 4. watching at 1.5x makes it more funny! ;)
hahaha...I was going to write a similar comment
Tushar, how would we solve if we got question saying, do not consider last row penalisation, that is wheneve is in last row at as long as it fits size lets sayy 10, it wont get penalised.
how do we implement this?
ohk tushar , i found box stacking problem too. thanks ur vedios help a ton.and u look good in specs
I didn't fully understand at first, but after re-watching and writing out the algorithm along with the video, it all makes sense now!
Hey Maxwell, This problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
You could do it in O(nm) where m is the max length of one line.
Make a matrix sized [n][m/2]. Now every [i][j] stands for the words i-j to i.
I was traversing so many places to learn dynamic program but at last these video lectures made my job easy and understandable...awesome, thanks a lot
I wasn't able to wrap this solution around my head . Thanks for the explanation!
Can you tell me how he store 5 in result array?
Why square? What is the justification?
Thanks a lot. As an extension of this i have one question. Given width and number of rows, how many times you can fit in that sentence? Next sentence can start after a space from last word. It will be helpful if you share the technique. Once again thank you.
couldn't understand it clearly :(
Thank you Tushar, your videos are really helpful :)
How is this method called "dynamic programming"? thanks
It starts from the lowest subproblem and moves to the highest problem, that's why. This problem has been explained beautifully in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
U explained it in very good manner. Thanks a lot.
Thank you Tushar, nice explanation... :)
kindly Explain RNA secondary Structure as well please !!
Thank you ! :)
How the recursion tree looks like?
very great explanation of the question. Thank you a lot.
at 11:05 it should be 49 + 9 (best you can do from j = 2 till end), or am I missing something?
Can you tell me how he store 5 in result array?
6:21 "10 - 2 is 4"
you heard it here boys.
Stop nitpicking. Making videos ain't a piece of cake. It was 10 - 8 = 2 extra spaces. Cost = 2^2 = 4.
Thanks for the note. but it was not clear
Hi, no worries - this problem has been explained clearly in my channel and students are really complementing the explanation. Just check it out ruclips.net/video/CMLsju1IPNI/видео.html
salute
Thanks for such a nice video :)
Thank you, Tushar! This is awesome
awesome job tushar!! have to say yours is the best tool for learning dynammic programming I have across simple and efficient at the same time! keep up the good work man! you are helping out so many people like me, thanks for that!
Can you tell me how he store 5 in result array?
Great work, thx for your help.
For those trying to use recurrence relation mentioned at the end to solve the problem, m[n] or m[len] or m[5](in this particular example) is 0
Thanks tushar...good job!!!
Thanks a ton Tushar :)))))
Good job
Nice explanation.
Great video Tushar!
Спасибо за видео
that is a great video , helped me a lot ! thank u
ola hu uber
Спасибо за видео