Editorial for DMOPC '22 Contest 1 P3 - Group Project
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1 Hint 1
We have a definition from the statement that works on the graph, but not the one in the input. Try to find an equivalent characterization for the complement graph (the one in the input).
Subtask 1 Hint 2
Try drawing a complete graph of size and remove edges until there are no friend groups.
Subtask 1
If there is a node in the complement graph with at least two neighbours, and one of the neighbours has at least two neighbours, there is no friend group. Suppose is the other neighbour of , and let be the other neighbour of . If , our group of four is , where is any other node. If , our group of four is .
Implementing this gives us an algorithm.
Subtask 2 Hint 1
Nothing particularly new needs to be done, all that needs to be done is figuring out how to maintain the information dynamically.
Subtask 2 Hint 2
Call a node heavy if it has at least two neighbours. Maintain the set of heavy nodes, along with another set.
Subtask 2 Hint 3
Call an edge strong if it connects two heavy nodes. If we have a strong edge, we can make a group without a friend group.
Subtask 2
The only missing piece of the puzzle is how to maintain this. We can use two sets. Updating the set of strong edges is cheap because whenever a node becomes heavy/light, there are only or neighbours to check and update.
Comments