Woburn Challenge 2017-18 Round 4 - Senior Division

Problem 4: Alpha Nerd

After hours of exciting offscreen action (not described in this contest), the Infinity War has just about reached its conclusion, with Thanos defeated and the Avengers preparing to give a series of inspirational speeches! One important question remains – which heroes should receive the most credit for the victory? With so many superheroes crammed into a single adventure, there simply won't be enough recognition to go around!

For instance, who should receive credit for being the Avengers' alpha nerd, playing the most important tech-related role? Iron Man is the obvious choice, but Spiderman has been studying computer science for a whole few months and wants a shot at the title as well! This prospect annoys Iron Man, so he plans to give Spiderman a competitive programming problem to put him in his place. He'll even give him a nice, easy one – computing the weight of a graph's minimum spanning tree.

Iron Man will generate a complete, undirected, weighted graph with N (2 ≤ N ≤ 300,000) nodes, numbered from 1 to N. Each of its N×(N − 1)/2 edges will be given a weight of either 0 or 1. Iron Man has already decided on the weights of M (0 ≤ M ≤ N − 1) of its edges – in particular, the edge connecting nodes A_i and B_i (1 ≤ A_i, B_i ≤ N) will have a weight of 0. The M fixed edges are all distinct, and there are no cycles amongst them. Each of the remaining edges in the graph will randomly receive a weight of either 0 or 1.

Spiderman is feeling confident about this challenge, having just learned about Prim's algorithm for constructing minimum spanning trees in school. Unfortunately, he's misremembered the algorithm! His version involves starting at a random node and greedily following minimum-weight edges around the graph until he's constructed a path which passes through all N nodes. In pseudocode:

1. Set c to be a random node between 1 and N, inclusive.
2. Mark node c as visited.
3. If all N nodes have been visited, terminate the algorithm.
4. Find the minimum-weight edge which connects node c to some unvisited node i (in the case of tied minimum weights, choose a random minimum-weight edge).
5. Add the edge between nodes c and i to the minimum spanning tree.
6. Set c to be equal to i.
7. Return to step 2.

This algorithm will always terminate and produce a valid spanning tree on the graph, but said spanning tree may not end up having the minimum possible weight at all. To some extent, this depends on how lucky Spiderman gets (in terms of what edge weights are randomly generated for the graph, which node is started at in Step 1 of the algorithm, and which tied minimum-weight edges are chosen in Step 4).

Assuming Spiderman gets as unlucky as possible, what could be the largest possible difference between the weight of the spanning tree returned by his algorithm, and the weight of the same graph's minimum spanning tree (which Prim's actual algorithm would return)?

Subtasks

In test cases worth 12/37 of the points, N ≤ 6.

Input Format

The first line of input consists of two space-separated integers, N and M.
M lines follow, the i-th of which consists of two space-separated integers, A_i and B_i, for i = 1..M.

Output Format

Output a single integer, the maximum possible difference between the algorithm's answer and the weight of the graph's actual minimum spanning tree.

Sample Input 1

3 1
1 2

Sample Output 1

1

Sample Input 2

5 3
3 1
1 5
2 1

Sample Output 2

3

Sample Explanations

In the first case, it's possible that the edge between nodes 1 and 3 could receive a weight of 1, while the edge between nodes 2 and 3 could receive a weight of 0. It's then possible that Spiderman's algorithm could start at node 2, then randomly choose the weight-0 edge leading to node 1, and finally be forced to choose the weight-1 edge leading to node 3 before terminating. This spanning tree (2 ↔ 1 ↔ 3) has a total weight of 1, while the graph's minimum spanning tree (1 ↔ 2 ↔ 3) has a total weight of 0.

In the second case, it's possible that Spiderman's algorithm may produce a spanning tree with weight 3 greater than the minimum spanning tree.

All Submissions
Best Solutions

Point Value: 18 (partial)
Time Limit: 4.00s
Memory Limit: 64M
Added: Apr 20, 2018
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

For those looking for an additional challenge, a more difficult version of this problem is available at [url]https://wcipeg.com/problem/wc174s4h[/url].