CliqueCuts
2016 TCO Algo 2A · 2016-03-24 · by lg5293
Problem Statement
Alice and Bob play a game using an undirected weighted graph. The graph has no self-loops and no multiple edges. The graph has n nodes. The nodes are numbered 0 through n-1.
You are given the
In the first step of the game Alice chooses a nonempty subset of the nodes of the graph and paints them red. This subset must form a clique in the graph. (I.e., each pair of nodes selected by Alice must be connected by an edge. Specifically, Alice is allowed to select any single node. Alice is also allowed to select all nodes, if the entire graph is a clique.)
Next, Bob colors all the remaining nodes blue. These nodes are not required to form a clique.
Alice's score is the sum of weights of all edges that have both endpoints red. Similarly, Bob's score is the sum of weights of all edges that have both endpoints blue. The result of the game is computed as Alice's score minus Bob's score. Note that the result of the game may be negative.
Given the graph, consider all valid sets of vertices Alice can choose. For each of those sets we can compute the result of the game. Let S be the sum of all those results. Compute and return the value (S modulo 1,000,000,007).
Constraints
- n will be between 2 and 45, inclusive.
- m will be between 0 and n*(n-1)/2, inclusive.
- a,b,c will each have exactly m elements each.
- Each element of a,b will be between 0 and n-1, inclusive.
- Each element of c will be between 0 and 10^9, inclusive.
- The edges (a[i], b[i]) form a simple undirected graph with no self-loops or multiple edges.
2
{0}
{1}
{100}
Returns: 100
The graph has 2 nodes and a single edge: the edge 0-1 with weight 100. Alice has three valid choices: she can choose either {0}, or {1}, or {0,1}. In the first case: Alice's score is 0, Bob's score is 0, hence the result of the game is 0-0 = 0. In the second case: Alice's score is 0, Bob's score is 0, hence the result of the game is 0-0 = 0. In the third case: Alice's score is 100, Bob's score is 0, hence the result of the game is 100-0 = 100. The sum of all possible results is S = 0 + 0 + 100 = 100.
5
{0,0,0,0,1,1,1,2,2,3}
{1,2,3,4,2,3,4,3,4,4}
{0,1,2,3,4,5,6,7,8,9}
Returns: 45
5
{0,1,2,3}
{1,2,3,4}
{9,2,4,3}
Returns: 999999941
This graph is the line 0-1-2-3-4. The edge weights are 9, 2, 4, and 3, respectively. As there is no triangle in this graph, Alice can only choose either a single vertex or two adjacent vertices. Thus, she has the following options: {0}, {1}, {2}, {3}, {4}, {0,1}, {1,2}, {2,3}, and {3,4}. Alice's scores in these cases are 0, 0, 0, 0, 0, 9, 2, 4, and 3. Bob's corresponding scores are 9, 7, 12, 11, 15, 7, 3, 9, and 11. Thus, there are nine possible results of the game: -9, -7, -12, -11, -15, 2, -1, -5, and -8, which gives us S = -66. As we are supposed to return S modulo 1,000,000,007, the correct return value is 999,999,941.
10
{0,1,2,9,5,3,4,7,3,4,1,5,2,3,0,7,8}
{6,7,4,5,6,2,6,3,1,8,2,0,9,9,8,2,5}
{10000,10000000,100000000,100,10,1,1000,100,10000,100,10000,1000,100,10,100,100000000,10}
Returns: 209370454
45
{}
{}
{}
Returns: 0
Submissions are judged against all 19 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CliqueCuts with a public method int sum(int n, vector<int> a, vector<int> b, vector<int> c) · 19 test cases · 2 s / 256 MB per case