PROBLEM LINK:Author: Shiplu Hawlader DIFFICULTY:MEDIUMHARD PREREQUISITES:Graphs PROBLEM:There will be two teams (Radiant and Dire) each consisting of N players. There are 2N players. One team has players (1,3,...2N1) and other team has (0,2,...2N2). There teams have not yet been assigned to Radiant or Dire. We have both options. Some of the players are friends and power of their friendship is given. Some elite players are to be selected (atleast 1). Elite player cannot have a friendship with a nonelite player. Friendships can be broken. EXPLANATION:Since each Radiant player should have elite number of friends (ie. at least 1) and nonelite players cannot be friends with elite players, all Radiant players should be elite. We will first fix team with players (0,2,...2N2) as Radiant and find the minimum total friendship of elite players and then do viceversa and take the minimum of the two cases. Now, there can be two cases.
In case 1, Example:
If we do a matching in this graph, we cannot include all nodes. So we make a complete graph of the same graph. Those nodes which don't have any edge between them are now connected by a edge of weight equivalent to shortest path between them.
So, we get a matching (ab) and (cd). Here (cd) is equivalent to the path (cad). Now, case 2, we have some elite players in Dire side. So, the general idea here would be to why not just ignore the Dire nodes( like convert this case to case 1), because we are reducing edges here and we have to reduce total friendship of elite nodes. But this would be wrong, here is an example. Suppose two Radiant nodes a and b are connected (ab) in one arrangement. We have another arrangement (acdb) where c,d are Dire elite nodes. It is possible that second arrangement is less costly than the first one. To build the complete graph, we can use any shortest path algorithm like FloydWarshall etc. Now we come to the part of minimum weighted matching in a general graph. We can do this by Dynamic Programming. We have a graph of N nodes and we need to do matching such that no two edges share same vertex and we have to minimise the sum of weight of final edges. We keep a bitmask M whose i'th bit is 1 if the node with index i has been already matched. Pseudo code:
We can use memoization in above pseudo code. So complexity here would be O ( N * (2^N) ). Testcases were set in a way that O ( N * N * (2^N) ) gives TLE. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 17 Feb '14, 00:23

Not sure if this is said at any point, but I feel it should be said explicitly: there is no point in not making all players elite (and it makes thinking about the problem much easier). answered 17 Feb '14, 02:48
