What's up, everyone?
This is Amy.
And as you have requested, we are going to solve a problem from code forces.
It is called MARBLE'S and it is an E problem from a deve to root mono.
Karpe is our main character here.
And he has arranged and colored marbles in a row.
His main goal is to rearrange these marbles in such a way that all marbles of the same color form a
contiguous segment.
And there is only one such segment for each color.
And to achieve this, he can do the following operation any number of times.
He can choose to neighbouring marbles and swap them.
We have to calculate the minimum number of operations Monarch proposed to perform to rearrange the marbles.
Note that the order of segments of marbles having equal color does not matter.
It is only required that for every color, all the marbles of this color.
For exactly one continuous segment, we have these seven marbles which are free for two, three, four,
two and two.
And the answer is free.
And let's see why.
On the first operation, I can just swap this marble of color too, with its neighbor of color free
or the second operation.
I can just swap these two marbles.
And the result is going to look like this.
And of course, for the last operation, I would just swap these two marbles.
And the result looks like this.
And this is it.
Now that we have understood the statement and the example, I highly suggest to post this video and
think about the problem, because the solution is really nice.
I surely enjoyed my time thinking about it.
Let's count how many times each color appears among these and marbles.
We are doing this because each possible solution is, in fact a permutation of these colors.
For example, this permutation corresponds to the following solution.
We take the first color, which is free, and we see that it appears two times.
So we push color free two times.
We take a look at the next color, which is four, and it appears for two times.
So we will push for two times in our solution.
And the last caller is two, which appears three times.
So two, two and two.
If we choose, for example, this permutation, this corresponds to the following solution.
So we need to find the permutation of this color.
As it takes as few operations as possible to transform the initial array of marbles into the corresponding
one of that permutation.
So we might start with a brute force approach in which we try each possible permutation of these colors,
compute the cost of transforming the initial array into the corresponding one and take the minimum out
of those.
But the question is how to actually compute the number of swaps needed in order to transform the initial
array into the corresponding one.
Let's say we chose the permutation free for two.
As you can see, I have to make sure that all the marbles of color free appear before all the marbles
of color for all the marbles of color free appear before all the marbles of color too, and all the
marbles of color.
Four appear before all the marbles of color too.
So let's take the first pair free and four.
And let's suppose I take a look at this array, but I ignore the marbles of other colors, then free
and for my array is going to look like this.
So there is one operation that I need to perform in order for color, free to be before color.
For now, let's consider the next pair free and two.
And consider the initial array.
But ignoring all the colors which are not free and to the array is going to look like this.
I have to make sure that color free appears before color too.
So one swap is going to be needed here.
And let's take the last pair for Antrel.
I will also need one swap in order to make this right.
I will swap the marble, too, with this marble, for if we add this up together, we get to a total
of free swaps, which is indeed the minimal number of swaps in order to transform this initial array
into the desired one.
So what we need to do here is to compute the following two dimensional array and let's call it MIN Swaps,
which is going to take two arguments.
I and J.
And its meaning is the following one, the minimal number of swaps needed to make sure that all the
marbles of color I are going to appear before all the marbles of color.
Gee, this can be performed pretty easily using a technique such as two pointers.
So it's going to be your homework.
So let's say we have computed the mean swaps, two dimensional array.
And here comes the fun part, guys, because we are going to solve this problem using subset dynamic
programming and we will build a one dimensional array DEPI where its meaning is DPF mask is the minimum
number of swaps needed to correctly order all the marbles of the colors in the subset mosque.
Mosque is going to be a natural number between zero and two at Power 20.
And it's binary form is going to represent our subset of colors.
For example, if mass equals 20, here is how it's binary form is going to look.
We will have 20 bits starting from the right to the left.
Indexing by zero, so zero, one, two and so on.
And here each beat represents one color, right?
So if our colors are one indexed, let's say from one to 20 here.
Let's suppose we will index our cards from zero to 19.
So we are going to take a look at what beats are set to one.
And here four is said one and two is set to one.
So our subset is going to consist of colors two and four.
Now, let's move on and find the recurrence relation for DBP, for each DEPI of the mask.
We are going to see what are the beats said to one in that mask.
So this is our subset of colors.
When building this dynamic programming, we basically started from scratch.
DEPI of zero, which means we don't have any color chosen.
Then we are sitting at each step some B two one.
So we insert one color to this subset.
Now we don't know the order in which we have inserted this color.
But that doesn't really matter.
For some DEPI of mask, we will insert into this subset a color which is not inserted yet.
And when doing this, we basically take the permutation of this key existing colors and pushing this
new color into the permutation.
Now, remember from earlier that each possible solution to this problem is actually a permutation of
this colors.
And the cost of each permutation is the sum of the values in that mean swaps array.
We have computed for each pair of colors.
I n g where I appears before J.
In the permutation the cost of the initial permutation.
Was already computed in DP of Mask.
But we will have to add the cost given by each of these new Quaye pairs.
So we will start building the DP from DP of zero equals zero, and for each DP of mask, we will try
to insert each possible new color into the permutation.
So we try each beat J, which is set to zero in the mask.
And for each of these G, we are going to update the DP value of the new mask.
We've done it cost.
Only if this new cost is better and the value of the new cost is, first of all, DEPI of mask plus
the sum of the costs given by the new pairs.
And let's call it some.
So sum is equal to the sum of all the means swaps of i n g where I is a bit set to one in the mask.
So I.
Is an already inserted color in the subset.
And J is the new color.
We add of course the final and sort of the problem is going to be DP of.
To add power 20 minus one.
So basically the subset consisting of all the colors between zero and 19.
And don't worry if there is any color of these, which doesn't appear in our array, the means swaps
of that color and every other color are going to be zero.
So they won't affect our DP.
And the time complexity is to add power.
K Cross, the K Square where K is the number of colors for our problem, K is 20.
But it can easily be converted into a better one.
Which is to add power K crossed K.
And this is also going to be your homework.
But one hint that I'm going to give you is to go to this sum.
And instead of computing it in Bigo of K, because you basically trought each eye where AI is a bit
set to one, try to compute this in constant time.
All right, guys, this was the problem marble's from code forces.
I really enjoyed solving it.
It is a super nice subset, dynamic programming.
And if you did too.
Don't forget to hit that like button.
Don't forget to subscribe and hit the notification belly button to be updated with my last videos and
share it among friends.
I'll see you the next line.
India.