What's up, Codders, here on NALGO, P.D.A.
And the as I know it, and we are continuing the series in which I choose your favorite forces rounds
and we solve the problem that are really worth solving.
But we start with an announcement.
First of all, if you want to solve life's competitive programming, challenges and coding interview
questions on a daily basis and code along some of the greatest guys maybe on this planet, who knows?
Join the mastermind Facebook group.
Because they're gonna find a lot of awesome and super cool guys which share the same passion as yours.
So, yeah, make sure to join that.
And also, I am dropping a big project in the upcoming month for moms and I'm gonna need some great
Korder, which both knows how to think about problems or rights or competitive programming is highly
recommended here.
But it can be coding interview questions too.
Like you really know, you really should know how to think about problems and you have to be a great
coder, too.
So if you think that the way you code is not that important during interviews, please don't sign up
for this because I am going to need someone with a wiener mindset.
All right.
So you really have to be eager to learn new things.
You are going to learn a lot and you are going to help me making computer science great again.
But this is my last month.
Now, let's jump into problem F when you see this kind of problem, which is an F even it's a video
to around, you know, you are going to have some fun because it's not going to be an easy challenge.
But we'll make it simple.
We'll make it simple.
So in the statement, basically, you are given a tree, a big tree and you are given two definitions.
The one is definition of an independent set in.
The other one is an age induced sub graph.
I recommend you to take your time and read the statement and try to understand what's here and go for
the examples we want do that.
We don't have time for that.
What I am going to explain, what are what are these two definitions on my little blackboard?
So let's do it.
Let's start here with the first definition, which we are going to see.
What is an independent set of vertices?
So basically here, as you can see, I have a tree with 10 nodes.
And when you choose an independent set of vertices, you are basically choosing here some subset of
vertices.
Here I have 10 vertices.
So of course, there are 10 at par.
There are two add power, 10 total possibilities.
But for a set of nodes to be an independent said you can't have two nodes which share an age.
Right.
So which are adjacent?
Basically not.
Let's take some examples.
I can choose Vertex four, for example.
Right.
When I choose Vertex four to be in my independent set now I'm not able to choose C.
Six, seven, eight.
Or what?
Because they share because four shares and age with each of them.
So let's say I'm gonna choose ten, which is really good.
Then I can go here and choose free.
And if I choose free, I have blocked nodes one and five.
I'm not able to choose them.
So let's say I'm going to take two.
Right.
So basically, is any set of nodes.
Right.
Any set of nodes where you don't have two nodes to share on H.
Now let's go for the other definition, which is I think an age induced sub graph.
That was the term.
And believe me, it's really simple.
So on the previous definition, we basically have chosen a set of vertices which had to be independent.
Now here we are choosing a subset of edges.
And when I choose a subset of edges, I take those edges and the nodes that are adjacent to those edges.
So let's take an example.
Let's say I take age seven and 10.
Seventy nine.
So basically, I have chosen these free nodes.
Until now, I can take age four.
Six.
Of course.
And I can go down and take one, two and one free.
All right.
So those are the edges.
Let's take a look at the vertices.
The vertices are seven, nine and ten.
Four and six and one, two, three.
So as you can see here, I've basically chosen free sub trees, which are not connected.
This is what an age induced sub graph is.
All right.
So as you know, when I'm teaching these problems, I will give you hints.
So I really suggest you pause the video after I give you a hint and think about the problem further.
That's the best way to learn computer science.
So let's start.
Well, first hint is that this problem has kind of a complicated statement.
When problems have complicated statements, I like to make them simple because you can solve simple
problems or even simpler problems than the initial one.
So here, I don't like all these terms and definitions.
So I have to kind of rethink about the statement and reformulated, let's say, not for the independent
set.
I want to look at this in the following way.
Instead of choosing a set of vertices, I will take all these vertices and I will color them in white
and black.
And let's say here, all these vertices are black.
After I called them, the white vertices are going to represent our independence.
So let's say, for example, I choose to color this vertex number one, seven, five and six.
All right.
One, five, six and seven is our independence.
And of course, I can take four or free or something because it's not valid.
So I am basically coloring them or I can mark them as you wish.
We have zero or what.
Right.
So this is our zero, let's say.
Or could be one.
Mm hmm.
Let's say it's one.
All right.
So this is some one zero zero zero one.
And so on and so forth.
Now, let's think about the age induced sub graph in the following way, as we saw.
We basically have chosen some sub trees.
But I can think of this in the following way instead of choosing some sub trees.
I can take the whole tree.
And for each edge, I can either keep it or remove it.
For example, let's say I want to split this into this subtree, seven, nine, 10.
So I've basically chosen age seven nine and age 17, let's say.
And I don't know, let's say want to have these subtree one, three and five.
All right.
This is completely equivalent to removing age one to removing one four.
All right.
Removing this one, too.
This one, too.
And this one, too.
So I have removed every other age which doesn't belong to our war, to our subjects that we have chosen
instead of the old statement.
The new one sounds like this in how many ways I can coller nodes in zero or one and remove ages so that.
Well, let's take the first one.
The white nodes are our independent set and the city's independent.
If there are two nodes in that independent set which are adjacent.
So here.
No edge.
You envy where you and V are both equal to one or white or in the independent set, and the second constraint
here we have the edges.
Is the following one.
And this is a little bit tricky.
I bet a lot of you guys have kind of got it wrong here.
So basically, I can remove any age that I want.
But there is one little corner case here of which you might not have thought of.
And is the following one.
After I remove all this ages, I can end up having some mold.
Which is colored in white.
So is in my independence set.
And it had some edges or I know for now it looks like a sun.
And I have removed all of its edges.
So this is now a lonely not let's call it lowly note.
I can't have a lonely white not ality.
Why is this?
Because if this knot is in my independent set or in some independent set, this means that first of
all, it is in some age induced sub graph.
But if this note is in some age in this sub graph.
All right.
Whereas the aging sub graph does the name and the definition suggests it must have at least one edge.
Right.
But this one has no edge.
So you can't have a node which is in your independent set and is alone.
But so this is wrong.
You can have a node which is not in your independent set.
So he's black or zero and is alone.
Because this doesn't mean that that node should be a chosen sub graph.
It means you have removed the edges and you have chosen other sub graphs.
But when the node is white, it always implies that you have chosen it in a subway.
The contradiction there.
So I have to think about the number of ways to color the nodes and to remove the edges in order to not
have any of these nodes, lonely white nodes, as I call it.
And in order to not have an age in which both nodes are one, now we have this.
Statement.
Which is easier.
We are able to solve this problem, post the video right now and think about the solution.
I'll be back.
All right, guys.
So we have to count the number of ways of doing something on some tree.
I think it's not a surprise that it's going to be a dynamic programming country problem because it is.
So we have basically two constraints.
The first one about the coloring.
Right.
And the second one about that lowly white H.
And let's take the first one only.
And let's think about in how many ways can I color the nodes of this kind of tree in order to not have
two white nodes which are adjacent.
This is a classical problem.
And it's a classic dynamic programming country.
So stick with me here.
Like any dynamic programming on tree, of course, I'm going to have something like this.
DEPI of Node.
Right.
DEPI of Node.
The number of ways of doing.
Yeah they are.
They are.
They are on these nodes.
Subtree.
Now I'm gonna have one extra dimension which is going to be zero or one.
Zero or one.
So.
As I said, the number of ways.
Are they are they are down.
On that note ramp and zero means that mode is going to be colored in black.
And one, it means that I'm going to color it in white.
Of course, if I compute this dynamic programming, the answer is pretty simple, because if one is
the root, let's say I will have DEPI of one and zero plus DEPI of one and one, and I count all the
possibilities.
Now for the recurrence relation, let's delay this.
Okay.
At.
Let's think about DEPI of nodding zero.
When I want to compute DEPI of Lodin zero.
So I know let's say this is not.
I know I'm gonna color this note in black or I'm going to market a zero.
OK.
If I do this, that's cool, because my restriction is to not have two nodes which are marked as one
which are adjacent.
Right.
So basically I can go to my children and color them as I wish.
So what I do here is that I'll take the product of DEPI of Sun and I can either mark the sun a zero
or I can market this one.
It's cool either way.
So I'll make the some of this DEPI of Sun in zero plus DEPI of Sun and one.
And I'm going to multiply all of these together.
And this is my DEPI of Nothing Zero.
Now if you think about it, DEPI of Lodin one.
What is the difference here is that let's say no, this this one and I market is what now?
I have that constraint that comes into play because I can't take a children and market as one, too.
That's not good because they're adjacent.
So all the children have to be zero.
So here I have product.
DPM of some son, of course.
And always.
Here is zero.
Now, this is the recurrence solution for this.
I have the answer.
So if I want to solve the problem, we've only the first constraint.
It's super easy.
But what about both now?
Well, it has to be something like that.
But a little bit different.
And it is because now instead of colouring this, we have zero or one black or white.
I have basically two color the edges.
Two, because if I remove one age, I can market as one or color it in black, whatever.
If I keep it, I color it as white or market as zero.
So it's the same dynamic programming.
But I have to take the edges into account too.
And of course, the second constraint.
So let's go and write that DP or I could.
So I'm going to keep this NDB loading zero and more than one.
And let's think about those recurrence relations now.
And let's take the first one.
Now, when I see DEPI of Lodine Zero, I'm going to count in how many ways I can color double nodes
and the edges in the subtree of this node in order to satisfy both constraints.
So let's take the first on the view of more zero.
And let's say this is node and I've marked it a zero.
Right now, this node has some children.
These children could either be zero or one.
Let's take this one, for example.
Well, when I have chosen a son now, I basically know two things.
I know, of course, the son.
But I know I have the edge between these two.
All right, so each relation node son is actually giving me the son and the edge between them so I can
use in the same recurrence relation.
I can take advantage of it and color the edges, too.
And what am I doing here?
Well, basically, if this is zero, as we've seen, this can be zero.
The node or what, both are cool and the edge can be zero or one two.
So basically, if this is zero and.
I take this note as being zero.
So none of them are in my independent set.
I can either keep or remove this edge.
I really don't care.
It's cool, right?
The only problem is when the note is won and the sun is one, then I know that I can't keep this age.
So I have a lot of freedom here.
So what I'll do here basically is that I'm going to take DP of Sun.
And as we've seen, again, I can choose either Zero or DP of Sun and one.
Both of them are super cool.
After choosing this sun's color, I will choose if I take or remove this age, both of them are cool.
There are two possibilities.
So all I have to do here is just take this some.
And multiplied by two.
And now I've chosen the color of the sun.
I've chosen.
If I keep or remove this age and of course, I do this for every sun.
So it's going to be the product of this.
All right, cool.
Only that the only difference is that we multiply by two.
Well, not really, because the second constraint is coming into play.
And let's see if I choose my son to be one.
I have to take into consideration the possibility that this is going to be a lonely white child, because
if I choose this to be one and I choose to remove this age and when I come from DEPI of Sun and one,
I have actually removed these ages, too.
This is going to be a lonely wife.
So I really have to be careful on that.
And how do I solve this?
Well, of course, I have to subtract all the possibilities that lead to this scenario.
And how many?
All of those.
Well, this happens when I have DPF Sunim one.
Right.
But not only that, it's not just DEPI of Sun in one, because it's those scenarios from DPF Sunim,
one in which these ages are also removed.
So I'm going to need another dynamic programming for that to count.
Just that.
Exactly.
So let's say I'm going to have another deep of node.
So this is basically the same thing.
But is the number of solution where I have removed all the edges from this node to any son of his.
So coming back here.
All right.
If I computed two and I know it, what changes here is that I'm going to have like.
Though in the product, inside the product for each son, is this some cross to right?
So son of zero.
Crosstalk Plus DPF son of one cross.
Two.
But I'm going to subtract.
Here D.
Of Sun.
Right.
Because those are the scenarios in which sun remains a lonely white note.
And that's good.
That's the correct recurrence relation.
Going back to DEPI of note.
And one is going to be exactly the same product of not because let's say this is not.
And this is what because this is one, as we know.
I can't have any sun which is going to be one because they are adjacent and white, which is not cool.
So every sun has to be zero.
So it's basically a product of DEPI, of Sun and Zero.
Again, if this is zero and this is one, what should I do here?
Well, I can either keep or remove this edge, so I'll have cross to.
I can either keep or remove this age.
Doesn't that mean that I can have the son to be one true, but remove this age and they are both white.
But they are not adjacent anymore.
So it's all good, right?
And it is.
So it's DEPI of Son Zero crossed to.
Plus.
I can make the sun to be white so deeply of sun and of one.
But it's not crossed to anymore because I know that I surely have to remove the edge.
I don't get to choose this time.
But couldn't it be the case here that sun is a lowly white note?
And of course, again, because if I choose to color it in white and of course I remove this age.
If this node had some sons and this ages, all of them were removed, then it's exactly the same scenario.
So I have to subtract again here.
Of SAP, right?
And that's good.
So the only thing that needs to be computed right now is this deed of note.
And that's not hard at all because let me erase the zero.
Let's suppose this node is our node, right.
And as we know, we want to compute these setups.
Only when this node is one or colored in white.
Because if it's not white.
It can't be a lowly YJ node.
So I don't really care about the setup.
Right.
So this is why.
And one more thing.
I have removed each of these edges so I don't get to choose about these notes color.
I don't get to choose about the edges, but I get to choose about one thing about its sons.
So basically, for each son, it can be white or black, whatever, that age is removed.
So I don't really care.
And I have product of DEPI of Son of Zero Plus.
So DEPI of son of one.
So for each son, either white or black.
That's cool.
But the same question, can I have that setup in which some son is a white, lonely note?
And I can't because here when I choose the son to be white and because I know for sure that I remove
all this ages.
Maybe this son has also his age is removed, too.
So, again, I have to subtract here D of son.
Right.
And that's it.
These are the free recurrence relation.
Of course, the time and memory complexity are bigger of M because we are using two dimensional arrays.
But the second dimension is just zero or one.
So that's cool.
And of course, the recurrence relation are in constant time.
So everything's fine.
Now let's get to the coding part, which should be more fun.