SEAGRP - Editorial

editorial
, , ,
6

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 :smiley:

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.

5 Likes
7

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.

2 Likes
8

what i could derive from other contestants solution that they were selecting vertex having minimum size and then marking it,can somebody expain this concept to me as editorial does not clarifies the concept clearly(atleast to me)?

9

Most of the accepted code used maximum matching for bipartite graph algorithm… But there may be general graph in test case so how they were passed…

10

I too did a lot of Google searching for this problem but couldn’t clearly follow the blossom algorithm so tried brute forcing and much to my surprise it got accepted. Initially check if the number of vertices are even. If true, then check if any vertex has degree less than one. If all vertices have degree greater than zero, then sort the vertices based on their degrees and then try to find a solution by removing edges. Try this for every possible combination until a certain set of edge removals satisfy.

1 Like
11

Very interesting paper :

http://web.eecs.umich.edu/~pettie/matching/Lovasz-determinants-matching-1979.pdf

On page 3 :

In fact, results of Zippel [17] imply that the probability of error is less than m / N.

Thus choosing random values for the matrix between 1 and 1000 * M gives you a probabilistic answer >= 99.999%. :slight_smile:

4 Likes
12

I got away with a recursive brute force solution.
http://www.codechef.com/viewsolution/3173530

13

i can’t understand ,why is it giving wrong answer…(it runs fine on my compiler)
…
please help…
//www.codechef.com/JAN14/problems/SEAGRP/

#include
using namespace std;
#include<stdio.h>
#define max 100

int main()
{
int t,m,n,i,x,y;
scanf(“%d”,&t);
while(t–)
{
scanf(“%d%d”,&n,&m);
int f[max]={0},a[max]={0};
for(i=0 ; i<m ; i++)
{
scanf(“%d%d”,&x,&y);
f[x]++;
f[y]++;
}
for(i=1 ; i<=n ; i++)
{
a[f[i]]++;
}
for(i=1 ; i<=n ; i++)
{
if(a[i]%2 || f[i]==0)
break;
}
if(i==n+1)
printf(“Yes\n”);
else
printf(“No\n”);
}
return 0;
}

14

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.

15

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…

16

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.

1 Like
17

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.

18

understood thanks :slight_smile:

19

http://discuss.codechef.com/questions/4138/minesrev-editorial
You can see it.

20

I’m not trying to find the actual path but only checking if graph is Hamiltonian using Dirac’s Theorem and that is not NP-complete.

21

try this:
1
6 8
1 2
1 3
2 4
2 5
2 6
3 4
3 5
3 6
Answer is NO.

22

@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 CodeChef: Practical coding for everyone. 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.

1 Like
23

@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.

1 Like
24

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 !

25

Dunno. Sounds weird, it could correspond to a completely different graph.