Editorial for LCC '22 Contest 2 J5 - Be-leaf-ing in the Leafs


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: marsflat

If there are no trade pairs, nothing can be done so the maximum value is simply the current team's value.

If there is only one trade pair, we can check if the current team's value can be increased with the trade. This will happen if only one player is on the Leafs roster and the other player has a higher rating than the one on the Leafs. This is the solution to subtask 1.

Notice that each player can be represented as a player, and each trade pair can be represented as an edge, creating a graph. The major observation here is that any player u on the leafs roster can be traded for any player v not on the roster if it is possible to reach node v from node u with a path using the edges, so long as the path does not contain any players on the roster. With some thought, it can be seen that the last condition does not matter.

In subtask 2, the graph is connected as any player can be traded for any other player. Let the number of players on the Leafs roster be K. We can trade all K players for the K highest-rated players. If a player is part of the K highest-rated players, no trade is necessary.

For the full solution, the graph is disconnected (there are multiple connected components). We can use the same idea for subtask 2 for each connected component. Let K_i be the number of players in the i-th component that are on the Leafs roster. We can trade all K_i players for the K_i highest-rated players in that connected component, repeating for each connected component.

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.