PROBLEM LINK:Author: David Stolp 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 selfintersected 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 NPhard. 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 selfintersected. 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:
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 NPhard in undirected graph. Here, we introduce two ways to find the longest path. The framework is as following:
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 tradeoff. In the end, I would like to give you 3 more tips:
Any more awesome ideas are welcome to share in the replies. :) AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 13 Jan '14, 15:15

My solution mostly corresponds to what explained in the second part of the editorial. But instead of greedy or recursive search I use beam search with width equal to 1000 / N (dogscience). For cost of the edge I used euclidean and Manhattan distances  the greater the distance the better the edge. Don't ask me why  this is dog science as well :) As mentioned in editorial I run the tours search multiple times while time permits. To speed up the process I stop the particular run if (the number of paths in it) + (some basic estimate of the number of paths in the remaining graph) is >= (the current best solution). For basic estimate I take (max_degree + 1) / 2. The better one would be the sum of such values over all connected components. But it's timeexpensive and give worse score. Another small difference is that instead of taking some fixed edge I take some vertex and build the longest path starting from it. Also once the path is not extendable I try to extend it in opposite direction. My tours search has two modes. Random one  where at each step we take any vertex of positive degree and greedy one  where at each step we take the vertex of maximum degree. Since number of vertexes is below 64 I use bit masks technique to store the graph. See details in my solution. I cleaned up all testing stuff for readability. It scores 0.741 points. Regarding the testing stuff I want to mention that test generator here could take long time to generate tests with N close to 50, due to collinearity condition. So instead of generating them in each run I generated random 50 tests once and save them into file. answered 15 Jan '14, 10:46

Would anyone be kind enough to share their test case generator / verifier now that the contest is over ? My code was returning WA with some parameters and I wanted to investigate them further. It'd save me some time having to write my own .. sigh. answered 13 Jan '14, 18:31
1
http://ideone.com/GtOBV4 This is a very basic generator. It does not check for collinearity though it is unprobable. Also value of n has to be changed manually.
(13 Jan '14, 18:39)
1
I think you can look at some top solutions, they all have generator and verifier that you need. Also, it is not hard to implement it. I think implementing them now will be helpful for the next month's contest. :D
(13 Jan '14, 19:12)
Thank you, i'll look into it. A random test case generator shouldn't be hard, but one which ensures points are collinear, etc. And the verifier which ensures all the roads have been visited, and no road intersects would take a bit of an effort. I'm prepared to write one myself, but would've saved me a lot of effort if someone who already had done it for the contest, shared it with me.
(13 Jan '14, 22:20)
We can check these conditions and regenerate if some are violated.
(13 Jan '14, 22:38)

Can any of the top scorers or others explain how to use some of the other methods like using intersection between the segments or dfs method etc... P.S.: I have done it using the following method:
This method gave me a score of 0.447 (suggestions to the method i used are also welcomed) answered 13 Jan '14, 21:05
I used a similar approach to yours but with these diff.
(13 Jan '14, 22:06)
I tweaked values for kLimit and kThreshold to get more optimal results .. but unfortunately I didn't do much good either .607.
(13 Jan '14, 22:08)
whats this "kThreshold" ?
(13 Jan '14, 22:27)
Basically after you get the first tour (the set of connecting roads), you'll have to run the same algorithm again on the remaining roads till you get tours with all of them covered. I am only evaluating the best of 2 tours for first 'kThreshold' tours. For the remaining tours, the best solution is automatically selected. My reasoning was, that at that point, you'll have more discontinous sets ...
(13 Jan '14, 22:38)
Example psuedocode FindTours (tour_no) : repeat for kLimit times select a road expand it to both sides save the tour end if (tour_no > kThreshold) select best tour FindTour(tour_no + 1) return solution end repeat for 2 best tours select tour FindTour(tour_no + 1) save finalSolution end return with best out of two finalSolution end
(13 Jan '14, 22:45)
a good variant of my approach. the advantage you have with this method is there are more variables to play with.
(14 Jan '14, 08:57)
i hv used dfs aproach but i dont know y its giving wa pls can any tell me 1 first select vertex with min degree 2 from it start dfs till any vertex is left (excluding intersecting n repeated ones) n deleting these edges frm grph 3 repaeting 1 n 2 till min degree=0 link to my ans http://www.codechef.com/viewsolution/3249354
(14 Jan '14, 21:13)
showing 5 of 7
show all

i hv used dfs aproach but i dont know y its giving wa pls can any tell me 1 first select vertex with min degree 2 from it start dfs till any vertex is left (excluding intersecting n repeated ones) n deleting these edges frm grph 3 repaeting 1 n 2 till min degree=0 link to my ans http://www.codechef.com/viewsolution/3249354 answered 14 Jan '14, 21:13
