Editorial for LCC '22 Contest 2 J5 - Be-leaf-ing in the Leafs
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 .
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 on the leafs roster can be traded for any player not on the roster if it is possible to reach node from node 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 , the graph is connected as any player can be traded for any other player. Let the number of players on the Leafs roster be . We can trade all players for the highest-rated players. If a player is part of the 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 for each connected component. Let be the number of players in the -th component that are on the Leafs roster. We can trade all players for the highest-rated players in that connected component, repeating for each connected component.
Time Complexity:
Comments