Editorial for Leaders.


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.

Author: FrankHG

(Analysis by David Hu)

Note that each cow visits only cows at or after it. This implies that it is impossible for any pair of two cows to visit each other. Thus, either the leader of the guernseys must have visited all the guernseys or the leader of holsteins must have visited all the holsteins (or both). This means that the leader of the guernseys must be the earliest guernsey or the leader of the holsteins must be the earliest holstein (or both).

Once we fix the leader of the guernseys to be the earliest guernsey and verify that the earliest guernsey has indeed visited all the other guernseys, we can brute force over all holsteins and check whether they can also be a leader together with the earliest guernsey. Likewise, we also consider a similar case where the leader of the holsteins is the earliest holstein.

Make sure to pay special attention to the case where the earliest guernsey and earliest holstein are both leaders.


Comments

There are no comments at the moment.