Cool tree shuffling.
You probably know the statement.
It was super cool and cute problem.
I really enjoyed solving it.
So that's it.
And by the way, the problems with trees are my favorites.
So whatever code forces round that I have, which he has two or three problems with trees, I'm like,
that's my round.
That's my top round.
I'm gonna do like the best, the best lately because I just love trees.
Give me dynamic programming.
Give me greedy on trees.
I just love it.
So no more talk.
We are given a tree.
We have end nodes which is rooted in node one.
And each of these nodes has one binary digit zero or one initially and has a target digit.
Right.
So at the end, after performing a couple of operations, we need to have in that node, that target
digit.
And what is one operation?
One operation is selecting K nodes.
From the subtree of any node, you and shuffled the digit in these nodes as we wish, and the cost of
doing this is K crossed a of you.
So each node has a number A, which is the cost of picking that node subtree.
Then we pick K nodes.
We shuffle that.
And of course this K crossed eight.
And yeah, basically that's it.
Print the minimum cost to convert the tree into the final target tree.
Or minus one.
If it's impossible.
All right, guys.
So let me be honest with you.
A lot of you know me for a long time and are on the channel for kind of a long time.
And you all know two things about me.
First is that when I solve a problem, I always think about the simple version of it.
I'm gonna do that second, when a problem tells me print minus one.
If you can't do that, the first thing that I do is think about when should I print minus one.
That's my thing.
If some problem says, all right, it could be impossible to do it.
I think, like.
When is it impossible to date?
So this is what I do.
So I'm thinking about this problem, right?
I have a tree and.
Some notes are going to be already.
Okay.
Right.
So be equal.
See, the digit that is in that note is actually the desired digit.
Cool.
Those notes are going to be untouched.
I don't touch these notes.
I let them as they are because they are already key.
Right.
So what should be the point of picking one node which is already your key and changing its digit?
Right.
So shuffling swapping basically its value with another Nords value.
There is no point in doing that.
And then I thought.
There could be a point in doing that.
Let me explain.
If this note has value zero and it should be zero in the end.
And this note has value one, but should be zero.
Could it be possible to swap these two together?
Mm hmm.
It could be, but then I'm going to need an extra a..
We should, I think should be zero.
Yeah, should be zero.
Not essentially zero, sorry, and should be one.
So if I do this, I'm then going to swap these node with this one.
Right.
So I have one here and I have to get rid of the one and storeyed here and exchange it for a zero.
Cool.
So wherever these notes are, if the LCA.
What is LCA?
I think it's the least common ancestor or something like that.
But Elsie is the acronym for that.
So these two have an LCA.
These two have another LCA.
And these free together have another LCA.
Right.
So this is LCA one.
This is LTA two.
And this is LCA Free.
The great LCA.
All right.
Well, yeah, I think it's pretty obvious why swapping these two and then swapping these two is way
more expensive than swapping from the start.
These two.
Right.
It is because you pay to cross the course then.
And one.
Let's say.
Yeah, plus to cross the coast in L2 instead of to cross the coast in Elfriede or something like that.
So from the start I have already proven to myself that or I did the nodes that are already.
Okay, you are going to not touch that, right.
So then I think about this.
So I have these three of our nodes and I know what are the bad nodes.
Right.
A bad node is a node in which B is not equal to C.
So I have a couple of bad nodes, these bad nodes.
Are basically are of two types.
Right.
The first type is a bad node, which is zero and should be one.
Right.
And the second type is a no.
That is one.
It should be zero.
Right.
So bad node, bad node type number one is when B equals zero and C equals one.
So from zero, I should be a one.
And type number two is of course when B equals one.
And C equals zero.
Right.
So because what I do is that I take notes from the tree and I shuffle them together.
All the values in the initial tree are going to be the same with all the values in the final tree.
I don't change any values.
I just change their nodes.
Right.
So one thing that I really, really need to do is let's say I have exactly X nodes, bad nodes of type
one, which they are zero and should be one.
How many of these should I definitely have?
Of course, X because if I'm zero and I should be in the end the one.
I'm going take a value of one from here, from these notes, right?
I'm going to swap myself with one of those notes.
So it should be exactly X, right?
If this was X plus one or something like that, it's a right.
It's definitely a.
How do you call it a contradiction?
Right.
Because the number of nodes of one are not going to be equal to the another, even to the number of
nodes of one from the initial tree.
But they should be equal because I don't change the values, just the notes.
So.
All right.
This is it.
Right.
So if the number of bad nodes of type one is different than the number of bad nodes of type two.
I simply print minus one and I stop the algorithm.
Now, let's suppose they are equal, right?
I have the tree.
I count how many nodes have B equals zero and should be one.
How many of B equal one and should be zero.
And they are equal.
What is the next observation that I am going to perform.
Really simple.
Remember me?
Why do I do?
I think when it's impossible and I think about the simple scenario ever.
That's all I'm gonna do, man.
So Simplist scenario ever, which is X equals one.
I have one bad note of type one.
One bad load of type two.
What do I do?
I swap them together, obviously.
Right.
So let's say this is a bad note of type one.
So bad of type one.
And this is the bad note of type two.
Right.
In order to pick them together, I'm going to find their LCA.
Right.
Eh.
This is their LCA.
And because they are two, I'm gonna pay two crossed the cost of the node that I pick to be that you.
But be very careful that this you could be any node such that these two nodes are part of it subtree.
So could be the LCA, could be the LC aifs father, could be the LCAC grandfather and so on and so forth
all the way to the root.
Right.
So here I am actually going to pay to crust.
Not a of LCA, but the minimum between each and every node on the chain from the root to LCA.
So let's call it mean a the minimum age of LCA.
And as I've told you, the minimum age of some node.
Right.
Is going to be the minimum between each and every eight of some X where X is part of the chain from
the root.
All the way to that note.
Right.
So, again, if I pick two nodes and I find there LCA, I can pick as the node.
You want to know that I want from the LCA to the root.
This is super important because of course I'm going to pick the minimum one.
So the first thing that I know I'm going to do is that we a DFS, I'm gonna traverse the whole tree
and I'm gonna find this mean a it's super simple, right?
If I know the mean a of node, let's say if I know this mean a before calling DFS on the sun, I say
that.
All right.
Your mean A is the minimum between my mean A which I'm the father and your a right.
I know your moeny.
And then I can call the office from it.
So I compute this, let's say partial minimums or something like that.
And if I have only two nodes.
It's really simple.
All right.
What if I have four nodes?
That's an interesting question.
So what if X was actually equal to.
Right.
Well, it's simple.
If I have four nodes, let's just imagine four nodes.
These are the nodes.
Right.
And of course, two of them are going to be of type one.
Let's say type one, type one and other two of them are going to be of type two.
So these two.
Type one, these two, type two.
I basically have two possible scenarios.
The first one is that I pick all of these nodes in the same group.
And if I do that, I'm gonna find the LCA of all these four nodes.
Let's say this node.
This is the LCA.
And of course, I'm going to pay for because I have four nodes crossed mean a.
Of this LCA.
Right.
Another scenario is that I can pick.
The nodes in pairs, right?
Instead of taking all of them all for once.
I can take in the first group.
Two of them, maybe one with two, or maybe this one with that one.
And these two, it's my choice.
But the thing is that instead of taking all of them, I take pairs of them.
Which one do you think is better?
Does the question, should I take all four into the same group?
Or should I take them in groups of two?
What do you think?
Yeah, the second one.
Always, always, always.
I'm going to.
Beak.
Just to note, I'm going to pick a pair of notes.
Solve them.
Pick a pair of notes.
Swap them.
Pick a pair of notes.
Swap them.
Right.
And that's.
Let's let me explain why.
It's super simple.
You have to think about it.
Let's say this is not one.
This is not true.
And I pick them together.
They are going to have some LCA.
Right.
Let's call this L.C one.
Let's say this was the other node of the first type.
And this was the other one of the first type.
They are going to have another LCA.
Well.
If I pick them in pairs, I'm gonna pay true crossed mean a of LCA one plus two crossed mean a of LCA
two right instead.
If I didn't do that and I've taken all four of them.
One, two, one, two.
And they have common LCA.
Right.
This is the great LCA.
That is four crossed.
Mean A of the greater LCA, which you know is the thing.
This LCA is the LCA of these two.
Right.
So if you imagine these two have this LCA, these two have these LCA and these two have these LCA,
which is exactly this one.
Right.
So the fingers.
Mean A of L and mean A of L2 are less than or equal to this LCA.
Makes sense.
Of course it does, because let's remember, what is the definition of mean a right mean a of LCA one,
which is this one is the minimum between the value of a for each and every node from and one to the
root and for LCA is for each and every note from LCA to the root.
So in L1 I pick the minimum between the more values.
I have more options.
The minimum could be less than what it is in LCA.
So mean a of L.C one is always less than or equal to mean a of the great LCA.
And this is also true for LCA.
Two is less than or equal to mean a of the great LCA.
And I think this says it all because if these two are less than or equal to this one.
Of course to cross this one plus to cross this one is less than or equal then for cross this one.
Right.
And this is exactly why it is always optimal to choose pairs of bad nodes.
Right.
So, again, think about me a think again about why this is less than or equal to the meaning of the
greater SCA.
And if you figure out this, of course, the total cost is better, is less, is optimal.
When I choose the pairs, not all the nodes in one group.
So basically what I noticed by now is the following thing.
And by noticing this, I already got the solution.
I'm going to have X bad nodes of type one.
So X of Type one and X of type two.
And I'm going to take them into pairs one from here, one from here, one from here, one from here.
How will I do that?
I'm gonna do that as soon as possible.
Right.
Let me explain why.
As soon as possible, I see that I try always to take the pair of nodes which have the LCA as.
As close to them as possible.
Right.
So if this is an old one and this is an old tomb and this LCA are here, of course, I'm not gonna bear
this one.
We have another.
No.
Two if they're ALCS here, right?
Of course.
I'm gonna pair these two because this is the LCA, not these two, because the LCA is way farther than
this one.
Right.
So, again.
When a node is closer to another one.
No.
Let me put this in other words.
All right.
When the LCA is closer to those nodes, it is better, right, because we have seen that this mean A
is less than or equal than this one.
So I really want that.
I pick this pair of nodes such as the LCAC are as deep as possible.
Right.
And this is where I knew that I'm gonna go for a greedy approach.
I'm going to do a greedy approach in which you can basically imagine that you start from the leifs.
Right.
So you basically start from the leaves.
And each time you are in some node.
You think about this, all right?
This is not right.
If this is node, these are its sons.
In each of these sub trees, I'm going to have some bad notes.
Right.
So here I have some bad notes of type one and some bad notes of type two, bad notes of type one, bad
notes of two and so on and so forth.
The idea is that let's take these subtree, for example, if in this subtree, let's say not this one.
Right.
It's way more notes than that.
Let's say I have free bed notes of type one and six bad notes of type two in this subtree.
Right.
If I do that, this means that I'm gonna take this free of bed one and pair them with other free of
bed to from this subtree.
Right.
So I take free from here, free from here and free from here.
And I pair them together and I'm left with free beds, nodes of type two, which I'm going to propagate
to the root, to the node and I'm going to solve them.
Right.
So this is how I want you to imagine this really approach.
I want you to imagine that we want to solve the nodes as quick as possible.
We start from the leaves and we move up and want to pair these nodes as quick as possible.
Right.
So if I have two nodes, one and two.
If I can bear them, no, I'm going to do it right.
So when I when I'm in node, right, when I'm in node and I try out this sun, I found how many bed
one bed of type one and bed of type two nodes I have.
I bear as many as then that I can, in this case free.
I have free pairs here, which is basically going to be so free pairs.
What does it mean.
Free crust to crust mean a of that sun and so on and so forth.
Right.
So we are probably in order to explain this better, I should take away a more complicated example and
show you on paper.
But we don't really have time for that.
It will take at least half an hour more stuff like that.
But this is how entropy measure, right?
Take your pen and paper and take some example and think about starting from the leaves and moving up.
And when you find two nodes of type one and type two, you try to pair them together and you are going
to put them together in the LCA.