Johnny wants to increase his contribution.
Joining us, this magic called force use it right.
And as you know, the statement, basically he wants to write and different topics or any different
articles.
And each article should have a topic.
Right.
And basically, there are going to be exactly n articles.
And you have basically relations, right, between articles, which are they are they are die.
You basically know the answer or the statement, basically.
Let's get to the first input to be a little bit quicker or N is the number of articles and M is the
number of relations between articles.
Right.
A relation.
A and B means that they are related.
Let's say like this.
Right.
So basically what does he do.
He chooses.
Basically he starts from zero written articles and he chooses, which is the first article, which is
the second, the third and so on and so forth.
And when he chooses the Article X., he looks at all his neighbors and he's gonna pick the minimum minimum
number, which is not used by the neighbor.
Articles.
Right.
If this makes sense.
So basically, you are given this graph.
All right.
Let's cut to the chase.
There is no articles and topics and stuff like that.
It's a graph problem, right?
That's obvious.
So we are given a graph.
We have end nodes and M edges and we should pick a permutation permutation F of M nodes.
So permutation of length M.
Right.
And we have to pick this permutation in such a way that when we called the nodes, when we assign them
numbers, like it is said in the statement, like following that rule, we have to end up with the configuration
that we are given in the input.
Right.
So it's simple just to get the statement really clear.
Now, what I kind of liked and didn't like, let's say, about this round was that the problem were
a little bit too hard.
I mean, I want to be that guy who says it was too hard because I didn't solve them.
But I think the difference between these two in this one is very steep, like indeed.
Two.
It's kind of easy to solve.
ABC D.
Easy.
If you're, let's say, consider yourself a good coder when you're on leave, do your like a sort of
day.
And Dina managed to sort of be or something like that.
So yeah, it's a big difference.
But about this problem.
There are five hundred thousand nodes and five hundred thousands edges.
So obviously it should be something like greedy sort thing, constructive algorithms, stuff like that.
So let's go from my process of feeling.
Right.
I'm thinking about this problem and I'm like, all right, I have this graph.
And the nodes basically have colors or numbers.
Right.
And how can I pick them in order to be able to do this?
Well.
Let's put it like this.
I have my Photoshop create something new, untitled one.
I think you can see the screen right now.
So let's put it like this.
Let's say I have somewhere a node which has the number seven.
In order to be able when I choose this note, to color it, we have seven or two assign the number seven,
all of its neighbors.
Right.
There have to be at least six neighbors, which all of them have numbers.
What one of them to free this is free.
Free for five and six.
Right.
So this is my first idea, like, all right, I don't.
Let's say care about the specific value in a..
But I know for sure that for that value to be assigned.
I need all the neighbors.
To have assigned numbers from one to six.
Because if, let's say Freeh wasn't here, I couldn't assign seven.
I would have had to assign Freeh.
Right.
So at this point, I know one thing for sure.
When I want to choose a mode, we value X.
I have already chosen all the nodes.
We have values from one to X minus one.
That's definitely for sure.
After I thought about this, guess what?
I take a look at the inputs and outputs like the examples.
Right.
And I take a look at this one.
Hmm.
Two, five, one, three, four.
Are those nodes sorted by value?
Yeah, they are.
Right.
Now, two is one, Lord, five is one.
And then all of them are two.
And first example is exactly the same.
So when I notice this, I was like, all right.
So definitely a sort.
First thing I do, I'm gonna sort the nodes.
And if I sort the nodes by value.
I basically know the permutation, right?
I sort them.
I know the permutation.
That's it.
If it is possible, so after sorting the notes.
I still have to figure out if for some more configuration or input example, it is possible to actually
color or assign values to these notes correctly, given the graph.
Right.
So I still have to check that code.
So I'm like, all right, let's check that.
How do I do that?
Well, shouldn't be that hard, right?
I mean, I have sorted the notes increasingly.
Cool.
Then I can either read through each and every note.
Okay.
And when let's say I want to check this node, which has value X, what should I do?
What should I do if I have a node of value X.
I have to make sure that among all its neighbors, I have h each and every value between one and X minus
one.
OK.
Can I do this by brute force?
I mean, for each and every note.
Can I either read through each and every neighbor and see what values are there?
I think I can and I will explain why.
So I go for all the neighbors.
Neighbor one neighbor to neighbor free and so on and so forth.
And I see what values are there.
Basically I pick each and every venue and I store something like an unordered map.
Right.
Unordered map or a frequency array or however you wanna call it, just to see what are the values there.
So I'm in the north.
I iterate through the neighbors right after I'm finished.
I know the values that are among the neighbors and I just have to check if there are.
Exactly.
X minus one.
Different values which are less than or equal to X.
Right.
So this is another thing.
After I iterate for the neighbors and I basically mark the values as visited as true.
Why do I have to check?
Indian is that for this mode to be assigned the value X?
I have to take a look at his neighbors.
We have values less or equal than him, right?
So let's put it like this.
For each neighbor, let's call it, and for each neighbor and.
If the value of N is less or equal than X, right?
If its value is less or equal than X, Idont or something like frequency of that value equals through.
And one more thing, I'm going to count how many different values are among its neighbors.
And I'm going to do this using a variable.
I'm going to have a colander equal to zero.
And each time I visit a neighbor, I take a look at it, at its value.
And if the value is less or equal, then X.
Before setting the frequency.
True, I check if the frequency is false.
Because if that frequency is false, that means that this is the first time that I encountered that
value.
So I should increment the counter.
And in the end, after completing this for loop in the counter, I know how many different values.
Less or equal.
Then X are among the neighbors.
If this counter is equal to exactly X minus one, that means everything's fine.
If not, everything's not fine.
Because if I have exactly X minus one.
Different values.
Less or equal than X.
Right.
I have to make sure yes.
One more thing, which is very good.
I have to make sure that I don't have any neighbor which is equal to X.
Did they check that during the contest, was it the or.
All right.
So it's accepted.
All right.
Cool.
Wow.
If I have some X here among the neighbors, this is not OK.
So we'll take a look at my source code and we'll see if it actually is an accepted or not.
So, yeah.
So basically, that's it, right?
For each and every node, either it's for the neighbors, store them in a frequency array or in an order
map.
And check this counter.
I count how many different are.
And check to be exactly X minus one.
And why is this OK?
Because it seems like a brute force.
Right.
I take each and every node and I take them each and every neighbor.
Well, it's simple.
If I take each and every node and each and every neighbor.
What do I do here is that I take each and every edge place.
Right.
This could be common knowledge for you.
But actually, if we imagine a graph, a graph, we have notes and and some edges.
Right.
If I choose each and every node and iterate through each and every neighbor of this node, I basically
iterate through each and every edge twice.
So the total time complexity, something like N plus two crossed M.
Which is obviously Bego of and plus M.
So you're not gonna get time excited.
It's not a brute force approach.
You basically saw the nodes and to check if they are valid.
You brute force like this for each node and each neighbor.