UNIX> cp -r ~jplank/www-home/topcoder-writeups/2020/TheSocialNetwork .You can then compile to a.out by simply typing make.
# n m u v l Answer
0 6 6 {1, 2, 3, 4, 5, 6} {2, 3, 4, 5, 6, 1} {1, 7, 3, 4, 6, 12} 10 Edges [4,3] and [1,2]
1 5 7 {1, 1, 1, 2, 2, 3, 3} {5, 3, 2, 5, 3, 5, 4} {1, 8, 2, 3, 4, 6, 9} 28 Edges [2,3], [1,5] and [2,5]
2 7 6 {1, 1, 2, 2, 3, 3} {2, 3, 4, 5, 6, 7} {7, 11, 6, 9, 20, 15} 64 Edge [4,2]
Example 3:
n = 8, m = 11
u = {1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 7}
v = {2, 8, 3, 5, 4, 6, 7, 5, 6, 8, 8}
l = {2, 3, 1, 6, 11, 8, 9, 10, 7, 4, 5}
Returns 12: [3,6] and [1,2]
Example 4:
n = 13, m = 56
u = {1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5,
6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12}
v = {3, 4, 5, 7, 9, 12, 13, 3, 5, 8, 9, 10, 12, 13, 5, 6, 8, 9, 10, 11, 12, 5, 6, 7, 9, 11, 13, 7, 8, 9, 11, 12,
7, 8, 9, 10, 13, 8, 9, 10, 11, 12, 13, 9, 11, 12, 10, 11, 12, 13, 11, 12, 13, 12, 13, 13}
l = {82, 240, 395, 1041, 1165, 1274, 1540, 1650, 1904, 2306, 2508, 3162, 3380, 3637, 3778, 3913, 3971,
4101, 4148, 4218, 4394, 4434, 5107, 6147, 6280, 6337, 6461, 6490, 7056, 8024, 8373, 8924, 8961, 9058,
9304, 9359, 10899, 11049, 11090, 11174, 11269, 11356, 11547, 11808, 12566, 12591, 13322, 13447, 13667,
13672, 15013, 15319, 16153, 16447, 16454, 16470}
Returns 504663883
The driver program here takes a number on the command line -- here's how that corresponds to inputs:
Let's partition the edges into two sets:
One really easy way to implement the problem conceptually is to enumerate all possible S, and then choose the one with minimal cost. A power set will be too expensive, since m can be as big as 1000.
However, we can do a different, more efficient enumeration, which revolves around the fact that each edge has a unique cost that is a power of two. This fact gives us the following observation:
Let's try to "discover" S incrementally. We'll add two more sets to our enumeration U, which is the set of edges where we don't know whether they are in S or T, and C, which are edges that we've processed in U, and still don't know whether they are in S or T. Here's the algorithm:
U C S T U union T
-------------------- -------------------- -------------------- --------------------- ------------------
1-----\ X 1 X 1 X 1 X 1-----\
| \ 2 X X X X | \ 2
8| \ X X X X 8| \
| | X X X X | |
4------3--------2 X 4 3 2 X 4 3 2 X 4 3 2 X 4------3--------2
9 | 4 | X X X X 9 | 4 |
6| / X X X X 6| /
| / 3 X X X X | / 3
5-----/ X 5 X 5 X 5 X 5-----/
|
Let's consider the edges from smallest weight to biggest. We can see that if we remove [1,2] and [2,5], then U ∪ T is still connected. Let's add those edges to C:
U C S T U union T
-------------------- -------------------- -------------------- --------------------- ----------------
1 X 1-----\ X 1 X 1 X 1
| X \ 2 X X X |
8| X \ X X X 8|
| X | X X X |
4------3--------2 X 4 3 2 X 4 3 2 X 4 3 2 X 4------3--------2
9 | 4 X | X X X 9 | 4
6| X / X X X 6|
| X / 3 X X X |
5 X 5-----/ X 5 X 5 X 5
|
The next smallest edge is [2,3]. If we remove it from U, then U ∪ T is disconnected. That means that [2,3] must be in S and all of the remaining edges in U must be in T. We put them there, and then put all of the edges in C back into U:
U C S T U union T
-------------------- -------------------- -------------------- ------------------ ------------------
1-----\ X 1 X 1 X 1 X 1-----\
\ 2 X X X | X | \ 2
\ X X X 8| X 8| \
| X X X | X | |
4 3 2 X 4 3 2 X 4 3--------2 X 4------3 2 X 4------3 2
| X X 4 X 9 | X 9 | |
/ X X X 6| X 6| /
/ 3 X X X | X | / 3
5-----/ X 5 X 5 X 5 X 5-----/
|
We start over -- [1,2] doesn't disconnect U ∪ T, so we add it to C:
U C S T U union T
-------------------- -------------------- -------------------- ------------------ ------------------
1 X 1-----\ X 1 X 1 X 1
X \ X X | X |
X \ X X 8| X 8|
X | X X | X |
4 3 2 X 4 3 2 X 4 3--------2 X 4------3 2 X 4------3 2
| X X 4 X 9 | X 9 | |
/ X X X 6| X 6| /
/ 3 X X X | X | / 3
5-----/ X 5 X 5 X 5 X 5-----/
|
[2,5] does disconnect U ∪ T, so we add it to S, and add the edge in C back into U, and start over:
U C S T U union T
-------------------- -------------------- -------------------- ------------------ ------------------
1-----\ X 1 X 1 X 1 X 1-----\
\ 2 X X X | X | \ 2
\ X X X 8| X 8| \
| X X X | X | |
4 3 2 X 4 3 2 X 4 3--------2 X 4------3 2 X 4------3 2
X X 4 | X 9 | X 9 |
X X / X 6| X 6|
X X / X | X |
5 X 5 X 5-----/ 3 X 5 X 5
|
Now, [1,2] disconnects U ∪ T, so we add it to S:
U C S T U union T
-------------------- -------------------- -------------------- ------------------ ------------------
1 X 1 X 1-----\ 2 X 1 X 1
X X \ X | X |
X X \ X 8| X 8|
X X | X | X |
4 3 2 X 4 3 2 X 4 3--------2 X 4------3 2 X 4------3 2
X X 4 | X 9 | X 9 |
X X / X 6| X 6|
X X / X | X |
5 X 5 X 5-----/ 3 X 5 X 5
|
U ∪ T is disconnected, so we're done. The sum of the costs is ( 22 + 23 + 24 ) = 28.
This algorithm is expensive. If we use a DFS to test connectivity, then for each edge e in S, we will do DFS's for every edge whose cost is less than or equal to e. That ends up being in the O(m3) range. It may work, though, just because the edges in e will likely be small, and U ∪ T will disconnect pretty quickly.
I didn't program it up, though, because there's an easier and more efficient solution:
U S T
-------------------- -------------------- --------------------
1-----\ X 1 X 1
| \ 2 X X
8| \ X X
| | X X
4------3--------2 X 4 3 2 X 4 3 2
9 | 4 | X X
6| / X X
| / 3 X X
5-----/ X 5 X 5
|
We consider the node with the highest weight: [3,4]. If we add it to T, T will now have 4 disjoint sets and remain unconnected. So add it to T:
U S T
-------------------- -------------------- --------------------
1-----\ X 1 X 1
| \ 2 X X
8| \ X X
| | X X
4 3--------2 X 4 3 2 X 4------3 2
| 4 | X X 9
6| / X X
| / 3 X X
5-----/ X 5 X 5
|
Now we consider [1,3]. If we add it to T, T will now have 3 disjoint sets and remain unconnected. So add it to T:
U S T
-------------------- -------------------- --------------------
1-----\ X 1 X 1
\ 2 X X |
\ X X 8|
| X X |
4 3--------2 X 4 3 2 X 4------3 2
| 4 | X X 9
6| / X X
| / 3 X X
5-----/ X 5 X 5
|
Now we consider [3,4]. If we add it to T, T will now have 2 disjoint sets and still remain unconnected. So add it to T:
U S T
-------------------- -------------------- --------------------
1-----\ X 1 X 1
\ 2 X X |
\ X X 8|
| X X |
4 3--------2 X 4 3 2 X 4------3 2
4 | X X 9 |
/ X X 6|
/ 3 X X |
5-----/ X 5 X 5
|
Now we consider [2,3]. If we add it to T, T will have only one disjoint set -- it will be connected. So [2,3] must be in S. We add it:
U S T
-------------------- -------------------- --------------------
1-----\ X 1 X 1
\ 2 X X |
\ X X 8|
| X X |
4 3 2 X 4 3--------2 X 4------3 2
| X 4 X 9 |
/ X X 6|
/ 3 X X |
5-----/ X 5 X 5
|
Now we consider [2,5]. It will connect T, so we add it to S:
U S T
-------------------- -------------------- --------------------
1-----\ X 1 X 1
\ 2 X X |
\ X X 8|
| X X |
4 3 2 X 4 3--------2 X 4------3 2
X 4 | X 9 |
X / X 6|
X / 3 X |
5 X 5-----/ X 5
|
Finally, we consider [1,2]. It too will connect T, so we add it to S, and now we're done:
U S T
-------------------- -------------------- --------------------
1 X 1-----\ X 1
X \ 2 X |
X \ X 8|
X | X |
4 3 2 X 4 3--------2 X 4------3 2
X 4 | X 9 |
X / X 6|
X / 3 X |
5 X 5-----/ X 5
|
You'll note that we've determined the exact same S and T as before, but our running time is greatly diminished:
(As an aside, you have to deal with those large numbers, which is a pain -- just make the costs long longs, precalculate the modulo cost of each edge by sorting them first and then processing them in increasing order, and then when you're calculating the final cost, you also need to do the mod operation.)
UNIX> a.out 0 Cost([1,2]) = 2 Cost([3,4]) = 8 Cost([4,5]) = 16 Cost([5,6]) = 64 Cost([2,3]) = 128 Cost([6,1]) = 4096 Starting Components = 6 Add [6,1] to T - Components = 5 Add [2,3] to T - Components = 4 Add [5,6] to T - Components = 3 Add [4,5] to T - Components = 2 Add [3,4] to S Add [1,2] to S 10
UNIX> a.out 1 Cost([1,5]) = 2 Cost([1,2]) = 4 Cost([2,5]) = 8 Cost([2,3]) = 16 Cost([3,5]) = 64 Cost([1,3]) = 256 Cost([3,4]) = 512 Starting Components = 5 Add [3,4] to T - Components = 4 Add [1,3] to T - Components = 3 Add [3,5] to T - Components = 2 Add [2,3] to S Add [2,5] to S Add [1,2] to S Add [1,5] to T - Both nodes are in the same component 28
UNIX> a.out 2 Cost([2,4]) = 64 Cost([1,2]) = 128 Cost([2,5]) = 512 Cost([1,3]) = 2048 Cost([3,7]) = 32768 Cost([3,6]) = 1048576 Starting Components = 7 Add [3,6] to T - Components = 6 Add [3,7] to T - Components = 5 Add [1,3] to T - Components = 4 Add [2,5] to T - Components = 3 Add [1,2] to T - Components = 2 Add [2,4] to S 64
UNIX> a.out 3 Cost([2,3]) = 2 Cost([1,2]) = 4 Cost([1,8]) = 8 Cost([5,8]) = 16 Cost([7,8]) = 32 Cost([2,5]) = 64 Cost([5,6]) = 128 Cost([3,6]) = 256 Cost([3,7]) = 512 Cost([4,5]) = 1024 Cost([3,4]) = 2048 Starting Components = 8 Add [3,4] to T - Components = 7 Add [4,5] to T - Components = 6 Add [3,7] to T - Components = 5 Add [3,6] to T - Components = 4 Add [5,6] to T - Both nodes are in the same component Add [2,5] to T - Components = 3 Add [7,8] to T - Components = 2 Add [5,8] to T - Both nodes are in the same component Add [1,8] to S Add [1,2] to S Add [2,3] to T - Both nodes are in the same component 12
UNIX> a.out 4 Cost([1,3]) = 986564553 Cost([1,4]) = 401898087 Cost([1,5]) = 68717736 Cost([1,7]) = 747696942 Cost([1,9]) = 683364727 Cost([1,12]) = 519859880 Cost([1,13]) = 96561979 Cost([2,3]) = 12469751 Cost([2,5]) = 244835673 Cost([2,8]) = 921530482 Cost([2,9]) = 843630890 Cost([2,10]) = 383219829 Cost([2,12]) = 961959392 Cost([2,13]) = 385287321 Cost([3,5]) = 635606520 Cost([3,6]) = 95150012 Cost([3,8]) = 358772781 Cost([3,9]) = 897524783 Cost([3,10]) = 110410713 Cost([3,11]) = 806629587 Cost([3,12]) = 816899385 Cost([4,5]) = 230754059 Cost([4,6]) = 905613773 Cost([4,7]) = 982654836 Cost([4,9]) = 912560659 Cost([4,11]) = 968634473 Cost([4,13]) = 648103429 Cost([5,7]) = 561922116 Cost([5,8]) = 917158272 Cost([5,9]) = 549765713 Cost([5,11]) = 130137674 Cost([5,12]) = 769353581 Cost([6,7]) = 401531258 Cost([6,8]) = 699602682 Cost([6,9]) = 611935421 Cost([6,10]) = 318765254 Cost([6,13]) = 547213445 Cost([7,8]) = 420954247 Cost([7,9]) = 563523972 Cost([7,10]) = 597180462 Cost([7,11]) = 530573276 Cost([7,12]) = 610308662 Cost([7,13]) = 6838094 Cost([8,9]) = 389188837 Cost([8,11]) = 609320153 Cost([8,12]) = 496950359 Cost([9,10]) = 272903132 Cost([9,11]) = 958425494 Cost([9,12]) = 790683632 Cost([9,13]) = 301876049 Cost([10,11]) = 498537210 Cost([10,12]) = 767192951 Cost([10,13]) = 527186279 Cost([11,12]) = 454654231 Cost([11,13]) = 195741162 Cost([12,13]) = 92703036 Starting Components = 13 Add [12,13] to T - Components = 12 Add [11,13] to T - Components = 11 Add [11,12] to T - Both nodes are in the same component Add [10,13] to T - Components = 10 Add [10,12] to T - Both nodes are in the same component Add [10,11] to T - Both nodes are in the same component Add [9,13] to T - Components = 9 Add [9,12] to T - Both nodes are in the same component Add [9,11] to T - Both nodes are in the same component Add [9,10] to T - Both nodes are in the same component Add [8,12] to T - Components = 8 Add [8,11] to T - Both nodes are in the same component Add [8,9] to T - Both nodes are in the same component Add [7,13] to T - Components = 7 Add [7,12] to T - Both nodes are in the same component Add [7,11] to T - Both nodes are in the same component Add [7,10] to T - Both nodes are in the same component Add [7,9] to T - Both nodes are in the same component Add [7,8] to T - Both nodes are in the same component Add [6,13] to T - Components = 6 Add [6,10] to T - Both nodes are in the same component Add [6,9] to T - Both nodes are in the same component Add [6,8] to T - Both nodes are in the same component Add [6,7] to T - Both nodes are in the same component Add [5,12] to T - Components = 5 Add [5,11] to T - Both nodes are in the same component Add [5,9] to T - Both nodes are in the same component Add [5,8] to T - Both nodes are in the same component Add [5,7] to T - Both nodes are in the same component Add [4,13] to T - Components = 4 Add [4,11] to T - Both nodes are in the same component Add [4,9] to T - Both nodes are in the same component Add [4,7] to T - Both nodes are in the same component Add [4,6] to T - Both nodes are in the same component Add [4,5] to T - Both nodes are in the same component Add [3,12] to T - Components = 3 Add [3,11] to T - Both nodes are in the same component Add [3,10] to T - Both nodes are in the same component Add [3,9] to T - Both nodes are in the same component Add [3,8] to T - Both nodes are in the same component Add [3,6] to T - Both nodes are in the same component Add [3,5] to T - Both nodes are in the same component Add [2,13] to T - Components = 2 Add [2,12] to T - Both nodes are in the same component Add [2,10] to T - Both nodes are in the same component Add [2,9] to T - Both nodes are in the same component Add [2,8] to T - Both nodes are in the same component Add [2,5] to T - Both nodes are in the same component Add [2,3] to T - Both nodes are in the same component Add [1,13] to S Add [1,12] to S Add [1,9] to S Add [1,7] to S Add [1,5] to S Add [1,4] to S Add [1,3] to S 504663883 UNIX>