Chloe and the Cyber Attack
All submissions for this problem are available.
CTU (Counter Terrorist Unit) is under cyber attack from a strange group of hackers! Obviously they have critical information, and the entire network needs to be shut down as soon as possible. Chloe is in charge of the network, help her out!
The network consists of N nodes/servers. Initially each node is connected to every other node. Each node has a cost associated with it denoted by C[u]. The shutdown of the nodes needs to be done in stages.
In one stage, consider nodes that have not been shutdown yet. A non-empty subset of these nodes are chosen and shutdown. The time required to remove these nodes is defined as follows:
Let the nodes chosen to be shutdown be in an active state. Let the other nodes(not yet shutdown) be in an inactive state.
To make the chosen nodes active, it takes C[u] time for each node u which is chosen.
To remove the chosen nodes, all connections involving these nodes must be removed.
To remove a connection between an active and inactive node, it takes C[u] seconds, where u is the active node.
To remove a connection between 2 active nodes, it takes C[u] + C[v] seconds, where u and v are the active nodes.
Note that all above connections are undirected, hence the connection between a pair of nodes is removed only once.
The total time taken for this stage, is the sum of the time taken to make the nodes active and the total time taken to remove each relevant connection mentioned above. After the shutdown, the chosen nodes are completely removed from the network, and do not affect subsequent stages. Also, Chloe is the only person assigned to do this job, hence at a time only one connection be broken.
Due to various constraints, the shutdown has to be done in exactly M stages . Help Chloe shutdown all the nodes in the minimum time possible, a lot of data is at stake!
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains 2 integers N and M , denoting the number of nodes and number of stages respectively.
- The second line contains N space-separated integers C1, C2, ..., AN denoting the cost of each node.
For each test case, output a single like containing an integer representing the minimum time needed to shut down the network.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 2000
- 1 ≤ M ≤ N
- 1 ≤ C[u] ≤ 100000
Input: 1 3 2 5 4 6 Output: 33
In the first stage, Chloe can choose 1st and 2nd node.
Time taken for this stage = Time taken to make nodes 1 and 2 active + Total time to break connections: (1 - 2,1 - 3,2 - 3). Total time = (5 + 4) + (9 + 5 + 4) = 27.
In the second stage, Chloe must choose the 3rd node.
Time taken for second stage = 6, since the 3rd node is the only node left.
Total time = 27 + 6 = 33
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions