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.
Lemma: If we have no information about the relative values of person
and person
, we must query for which of the two did better.
Proof: We can take any consistent ranklist where we have no relative information for these two individuals and collapse it into one where person
and person
are adjacent. If person
is between person
and person
, it cannot be the case that person
is forced to be between them, because that would imply the relative standing of person
and person
. Since person
is not forced to be between them, we can move them to be either above both individuals or below both individuals.
Now, given that we have a consistent ranklist and person
and
are adjacent, we can also swap them, since we are not forced to compare them. However, this means we have two ranklists that are consistent, which is in violation of the ranklist needing to be unique.
Therefore, we are required to do a relative comparison of every individual.
Consequently, it suffices to compute, for each pair of individuals, whether we know anything about their relative order. If we construct a graph where there's a directed edge from
to
if person
did better than person
, we can compute the number of unordered pairs
where
and
are not reachable from each other in either direction. The answer is therefore the number of such pairs.
To compute the reachability quickly, we can run BFS
times or use Floyd-Warshall.
Comments