TheSocialNetwork
SRM 790 · 2020-09-09 · by nikhil_chandak
Problem Statement
Alice and Bob came up with an idea for the next social network. Alas, Eve stole their idea and has already launched her network. Infuriated by this, Alice and Bob plan to take revenge by bringing it down.
The network is represented as an undirected connected graph with n users as the nodes and m (bidirectional) friendship links as the edges. Edge i connects the nodes u[i] and v[i]. Each edge is protected by some password: a string of bits. The password protecting edge i has length l[i].
They have found out an interesting feature about the passwords: Eve has implemented the social network in such a way that no two passwords have the same length (in bits) in order to make the network more resilient. Thus, all password lengths are distinct.
Bob would like to disable some of the friendship links in a way that will make the social network disconnected. (He hopes that this will make people stop using the network and thus Eve's business will fail.)
A link can be disabled with the correct password, which Bob doesn't have. Hence, he has no other choice but to search for the password in a brute-force manner. For simplicity, we will assume that the time he needs to disable link i is 2l[i].
Find the minimum time in which Bob can disable enough links to disconnect the social network. Return the answer modulo (109 + 7).
Notes
- The social network is connected if for any two users X, Y there is a sequence of one or more users Z1, ..., Zk such that Z1=X, Zk=Y, and each consecutive pair of users in the sequence are friends.
- The social network is disconnected if it is not connected.
Constraints
- n will be between 2 and 300, inclusive.
- m will be between 1 and 1000, inclusive.
- u, v and l will each contain exactly m elements.
- All elements of u and v will be between 1 and n, inclusive.
- The graph described by u and v will be simple: there will be no self-loops and no multiple edges between the same two nodes.
- The graph described by u and v will be connected.
- All elements of l will be between 1 and 105, inclusive.
- All elements of l will be distinct.
6
6
{1, 2, 3, 4, 5, 6}
{2, 3, 4, 5, 6, 1}
{1, 7, 3, 4, 6, 12}
Returns: 10
The given graph is a simple cycle of size 6. So, we need to remove at least 2 edges to disconnect the graph. In fact, removing any two edges will disconnect the network so it's best to attack those 2 edges' passwords whose total sum of time required is minimal. Hence, answer is 21 + 23 = 10.
5
7
{1, 1, 1, 2, 2, 3, 3}
{5, 3, 2, 5, 3, 5, 4}
{1, 8, 2, 3, 4, 6, 9}
Returns: 28
The given graph has one complete subgraph with 4 nodes and 1 extra edge to node 4. Although, disabling only 1 edge (4 --- 3) can disconnect the graph, the time required is 29 which is quite high and unoptimal. The best method is to remove disconnect vertex 2 from rest of the graph leading to the optimal time of 22 + 23 + 24 = 28.
7
6
{1, 1, 2, 2, 3, 3}
{2, 3, 4, 5, 6, 7}
{7, 11, 6, 9, 20, 15}
Returns: 64
The given graph is a tree so removing any edge disconnects the graph. Hence, the answer is the time required to guess the edge with minimal password length: 26 = 64.
2
1
{2}
{1}
{11}
Returns: 2048
#Add this as example if necessary.
8
11
{1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 7}
{2, 8, 3, 5, 4, 6, 7, 5, 6, 8, 8}
{2, 3, 1, 6, 11, 8, 9, 10, 7, 4, 5}
Returns: 12
5
4
{1, 1, 2, 3}
{2, 5, 3, 4}
{33360, 62331, 71358, 76647}
Returns: 397996577
PS: All the test cases after now on are generated.
Submissions are judged against all 102 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheSocialNetwork with a public method int minimumCut(int n, int m, vector<int> u, vector<int> v, vector<int> l) · 102 test cases · 2 s / 256 MB per case