PROBLEM LINK:
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
There an N astronauts, some who are infected by a parasite. You are given Q statements of the form (type,i,j).
- If type = 1, astronaut i accuses j of being a parasite.
- Else, astronaut i vouches for j being a human.
Also, it is known that a human never lies and a parasite never tells the truth. Determine if the statements made by the astronauts are consistent, and return the maximum possible number of parasites.
EXPLANATION:
Model the problem as a directed, edge-labelled graph.
Explanation
Let there be N nodes corresponding to the astronauts. For each statement (type,i,j), draw a directed edge from i to j with label type.
Make the edges undirected. Observe that this doesn’t lose any information.
Explanation
Claim: i accuses/vouches j \iff j accuses/vouches i.
| Type of directed edge (from i to j) | If i is a | then j is a |
|---|---|---|
| 1 (i accuses j) | Human | Parasite |
| 1 | Parasite | Human |
| 2 (i vouches j) | Human | Human |
| 2 | Parasite | Parasite |
You can manually verify the claim using the above table. For example, if i accuses j and i is a human, then j is a parasite; likewise, if j accused i and i is a human, then j is a parasite, holding to the initial statement.
The problem is now reduced to colouring the nodes (black for human, white for parasite) such that
- nodes connected by a 1 edge have different colours,
- nodes connected by a 2 edge have the same colour,
- the number of nodes coloured white is maximised.
For each connected component, there are exactly two valid colouring’s, if the statements are consistent.
Explanation
If no colouring exists, then the statements are inconsistent and we are done.
Otherwise, colour any arbitrary node black. By the above edge properties, all adjacent nodes are automatically assigned a colour and so on. Therefore, the colouring of the component can be uniquely determined by the colour of one node.
Also, the validity of the colouring isn’t affected, on inverting the colour of all nodes in the component.
Thus, there exists exactly two valid colouring’s, which can be determined by colouring a fixed node black or white.
The colouring of each component can be achieved by using a similar technique to bipartite colouring, with the difference being - the colour of an adjacent node is determined by the colour of the current node and the label of the edge connecting the nodes.
The final step is thus - for every component in the graph, find the number of white nodes when a fixed node is coloured black/white, and add the maximum over the two to the answer.
TIME COMPLEXITY:
Since for each connected component, we run DFS twice, the overall complexity is
where E is the number of edges, which is equal to Q.
SOLUTIONS:
Editorialist’s solution can be found here.
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters