Editorial for COCI '14 Contest 3 #2 Dom


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.

Let us observe that the problem can be represented with a graph: the nodes are going to be TV channels, and the pairs of favourite and hated channel of each pensioner are going to be directed edges from the hated to the favourite channel.

In case a channel is hated by more than one pensioner (and as such should have more than one edge coming out of it towards their favourite channels) it is sufficient to remember only one edge: the edge of the youngest pensioner because he is the one who gets up and changes the channel in this case.

Since the choice of changing the channels is now unambiguously defined, it is easy to come up with a solution: we traverse the constructed graph starting from the given channel P and count how many channels we changed so far (denoted by K) and which channels we've already viewed (already visited in our graph).

If we reach a channel we've visited before, it is obvious that the same channels are going to repeat (meaning we've entered a cycle) so the output is -1.

If we reach a channel that is hated by nobody (not a single edge is coming out of it towards another channel), the channels are going to stop changing so the total number of channel changes is K (movements in the graph), which is our solution.


Comments

There are no comments at the moment.