Editorial for DMOPC '16 Contest 2 P2 - Ebola Outbreak

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: jimgao, d

Knowledge required: complete search or disjoint set

When one has Ebola, everyone in his class can potentially get Ebola. With that observation, we can express each class as a set. When person i and j are in the same class, we can simply merge the 2 sets that i and j belongs to. Hence, the intended solution to this problem is to use disjoint set to manage the contents of the sets.

The disjoint set data structure has 2 operations \operatorname{Find}(a) and \operatorname{Merge}(a,b). When person i and j are in the same class, we can simply do \operatorname{Merge}(i,j). After processing all the classes, we can simply compare the value of \operatorname{Find}(1) and \operatorname{Find}(N) to determine if person N is infected.

A properly implemented disjoint set has a time complexity of \mathcal{O}(\alpha(N)) for each operation, where \alpha(N) is the Inverse Ackermann function, which is smaller than 5 for all reasonable values of N.

Time Complexity: \mathcal{O}(N + \sum K_i \alpha(N))

Alternate solution

Create a vertex for each student and each class. If a student is in a class, then create an edge between that student and that class. In total, there are N+M vertices and \sum K_i edges.

Next, do a graph search starting at student 1. Make sure to output the visited students. The visited classes can be ignored.

Time Complexity: \mathcal{O}(N + \sum K_i)


There are no comments at the moment.