The problem setting is exactly same as the perfect matching. That is, find a subset of edges, there are no edges have common nodes and all nodes are covered by one edge. Since the graph is general, Blossom algorithm which can provide the maximum matching in O(VE) time is enough.
Here, I would like to introduce a simpler way to solve this problem. Of course, it is not some strange greedy algorithms which may passed because we can’t design cases for all wrong solutions (contestants are always creative :D). Anyway, let me introduce the simple solution – Tutte matrix. We can randomly choose the X[i][j]. Since we only need to check whether its determinant is zero, we can module all number during Gaussian Elimination (used to calculate the determinant) by a big prime, such as 10^9 + 7. Due to the randomness, we can solve this problem with a high probability. This solution is O(V^3 log MOD), where MOD is the big prime number we chosen. O(log MOD) is caused by the calculating the inverse or elimination by subtracting.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Thanks for this very interesting problem and editorial… It was a joy to attempt to solve this problem during contest time and it is even better to read editorial and learn that there was a simple solution after all, which even used a standard algorithm.
I’m very interested now in reading more about the Blossom Algorithm and how it works so I can try to adapt it to solve this problem.
Do you happen to know of better resources to read about Blossom Algorithm besides wikipedia page?
I wanted to try Hungarian algorithm in this problem, but first had no time, and then got stucked with step 5, “Cover the zero elements with the minimum number of lines it is possible to cover them with.”, but to do this I have to solve matching problem as a subproblem (recursion?)…
The Hungarian algorithm is for bipartite graphs only (how do you convert a matrix to a multipartite graph, anyway?). And bipartite matching can be solved in O(N^3) using network flows, which is much simpler to code.
I tried following strategy (though I never got it correct). Can anybody point out why is this algorithm incorrect? What is wrong?
Before doing anything ensure that total no. of vertex is even otherwise output NO.
Lets work on a single connected component of our graph. The same procedure can be applied to all the components.
Find out all the leaf nodes (vertex with degree 1)
Now keep on removing the leaf edge one by one. Since, each leaf node(node with degree 1) can only be matched with the node it is allready connected with. So, at each step we will remove 2 nodes from the graph. So, the no. of nodes in the graph will always remain even. (This step may give arise to more leaf nodes. They must also be removed)
Repeat step 2 until following conditions are met:
If no leaves are left then we either have exhausted the graph or all we are left with a cycle or vertices with degree 0.
If the graph is exhausted then we are done(current component is matchable).
If any vertex with degree=0 left output NO.
If a cycle left then find the length of the cycle, If the length is odd then output NO otherwise the current component is matchable.
Something like this pictorially :
This is a very simple example. Here vertex 1 & 8 are the what I called leaf nodes. And edges {(1, 2), (7,8)} are what I called as leaf edges.
Why is this strategy incorrect?
My idea was to have 2N vertexes let say v1 and v2 for each v, and there is edge between v1[i] and v2[j] iff there is edge v[i] v[j] in original graph…
If we try to find if each of the connected components in the given graph has a Hamiltonian Path or not and also check if each of the components have even number of vertices, will this suffice to solve the problem ? Is this approach correct ?
I had initially thought of an approach exactly like yours. However i later realized that the the graph remaining is guaranteed to have atleast 1 cycle and will not always have exactly 1 cycle.There are many cases in which the remaining graph will consist of multiple cycles joined together for which your algorithm fails.
The approach will be correct however finding a Hamiltonian path in a graph is an NP-complete problem so it would have been difficult to get it accepted within the time limits.
I didn’t use a prime modulus or anything like that. I just chose random integers as variables of the Tutte matrix, and did the GEM on doubles. Chances are small that there’d always be an undetectably non-zero (or zero) solution
So I just try this an (insert constant here) amount of times and decide if the determinant can be non-zero.
That being said, this problem would’ve done better in a short contest. It’s hard to make worst-case test data, so wrong/slow solutions could pass, I think. Also, I solved it using Google Search algorithm, where I googled “perfect matching general graph” and got to Tutte matrix in no time. Overall, deciding if there’s a perfect matching in a graph sounds like a standard problem (and therefore solvable with hardly any effort by finding the solution), so it is a bit of a waste.
I think this problem tested google searching skills more than the programming knowledge. I know this was not intended but all one had to do to solve this problem was to figure out that it is a maximum matching problem in general graphs, search the same, find out about blossom algorithm and then search blossom algorithm code. Nevertheless it led me to many new algorithms and concepts. I read in norbert blum’s paper how a O(m*root(n)) complexity algorithm can find maximum matching in a general graph. If anyone solved the problem using this, please share your code.
@sayan_paul: No your algo won’t work…If you consider the follwing test-case:
1
8 8
1 2
2 3
3 4
4 5
5 6
6 4
4 7
7 8.
This test case will answer YES however it does not have any Hamiltonian Path.
@xellos0: could you please look into my submission http://www.codechef.com/viewsolution/3236313. I used the Tutte Matrix concept. But it gave me wrong answer. I think somehow I am not setting the correct indeterminants of the Tutte Matrix. Please suggest what is the exact way to set the indeterminants. Thanks in advance.
@m_a_y_a , i used a similar approach , there is one more special case when you have no vertex of degree one (a cycle) - you just can’t plainly tell that if the cycle is of even length then the current component can be matched
Look at this case,
graph with 10 vertices and 12 edges,
[[1 2],[2 3],[1 3],[4 5],[5 6],[4 6],[7 8],[8 9],[7 9],[10 3],[10 5],[10 7]]
The answer is NO even though this graph has no vertices with degree 0 or 1 and has an even length (contains cycles), you can’t match this graph.
In order to solve it, i used this approach, found an articulation point in the cycle and associated it with any one of its adjacent edges having odd cycle length and disconnect the graph. Then again follow the entire algorithm from the start on the remaining graph. Worked Out !
