PROBLEM LINK:
Author: David Stolp
Tester: Gerald Agapov
Editorialist: Jingbo Shang
DIFFICULTY:
Challenge
PREREQUISITES:
Greedy, Dynamic Programming, Search, Random
PROBLEM:
Given a undirected graph with N nodes and M edges, while each node is associated with a 2D coordinate, find minimum number of simple paths or cycles, which are not self-intersected and covered each edge exactly once.
EXPLANATION:
This is a challenge problem. The most important thing in solving challenge problem is to find some approximation/partial methods using the combination of search, greedy, dynamic programming, etcâŚ, because this challenge problem is NP-hard. Also, it is important to write a local test system to help you find the best strategy (almost all top ranked guys wrote their own test codes).
To solve this problem, first of all, we need to know why there is a restriction of the length of answer â should be smaller than or equal to (N+M)/2. That is because we can connect two edges share a common vertex as a path, which is definitely not self-intersected. Therefore, we can achieve the restriction of output.
And then, considering the special cases with smaller size. For example, if M is smaller than 15, we can use dynamic programming to get the perfect answer. First of all, generate all valid paths and cycles. They are distinguished by its set of edges (represented in a binary mask, 0âŚ2^M). And then, for a given subset S of edges, we enumerate all its subset check whether it is a possible path/cycle and update the optimal answer accordingly. More specifically, denote the minimum valid paths/cycles needed to exactly cover the edge set S as f[S]. The DP procedure is O(3^M) after we obtain all valid paths/cycles as following:
f[0] = 0; // it is an empty set
for S = 1 to 2^M - 1 {
f[S] = infinite
for (sub = S; sub > 0; sub = S & (sub - 1)) {
if (sub is a valid path/cycle) {
f[S] = min{ f[sub] + 1, f[S] }
}
}
}
The trick is to enumerate the sub via binary operations instead of 0âŚ2^M.
For the general cases, i.e. large N and M, we can find some greed ways. For example, intuitively, we may need to find out the longest valid path/cycle, remove them, and go on. Most of the top solutions during contest apply this idea or similar ideas. But, even finding the longest valid path/cycle is NP-hard in undirected graph. Here, we introduce two ways to find the longest path. The framework is as following:
while there is any edge remained in the graph {
longest = the longest valid path/cycle in the graph
remove longest from the graph
}
For both methods, we need to find some heuristic functions to rank the next edge to add to the current path. The most intuitive function is based on the intersections of other edges. It reflects how an edge conflicts with others, which means those edges will be invalid after we select this edge. Therefore, we can rank the edges in order. For the ties of edges, we can break them randomly.
The first method is Search. It takes a starting edge, and use dfs to expand the path as long as possible. The second method is Greedy, choose the best edges in each step. For Search, we also need to add constrains to the number of expanded solutions or the time it costs. Search may give better solution while Greedy is much faster. This is a trade-off.
In the end, I would like to give you 3 more tips:
- Due to the randomness of the order of edges, it will be better to run the algorithm multiple times to get a better score.
- Use different heuristic functions for different type of data or for different runs of the algorithm, may also benefit to your score.
- Implement your codes as fast as possible, such that it could be run more times in the time limit.
Any more awesome ideas are welcome to share in the replies. 
AUTHORâS AND TESTERâS SOLUTIONS:
Authorâs solution can be found here.
Testerâs solution can be found here.
