SEAGRP - Editorial

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

@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

@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

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 !

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

sambuddha: Are you only trying the determinant once? I did that at first, and got WA.

@xellos0:I donā€™t understandā€¦ I simply calculated the determinant of the Tutte Matrix using Gaussian Elemination with random pivot technique.
How many times do I have to calculate the determinant??? Are you trying to say that I have to generate the Tutte matrix and calculate the determinant of each connected component seperately???

@mecodesta can you please explain your solution

Iā€™m not talking about connected components. Do you know what a randomized algorithm is? Itā€™s something that can fail. The more test cases there are, the higher the chances of failing. The more times you try the same thing with different random values, the smaller the chance of failing. Maybe you just happened to choose the variables for which the determinant is 0, or maybe you just make a mistake somewhere :smiley:

@sambuddha ya correct, my algo fails to take leaf nodes into consideration.

Can someone point me to a better explanation about the Blossom algorithm or to give an explanation of it applied to this problem? I really want to code it now :slight_smile:

@sayan_paul My algorithm was to first eliminate all the leaf nodes using the steps mentioned by m_a_y_a above. Then You can use Diracā€™s Theorem as you said above to detect Hamiltonian path

Well, after googling and reading a bit, I got AC at last :smiley:

Maybe I write a tutorial about this when I have time :wink:

3 Likes

But in case of a cycle or many cycles if we take the vertex with the minimum degree(say A) and then find from the vertexes connected with it(A) the one with the minimum degree and make a pair with those two.
Is this approach correct, because the solution is getting accepted using this approach.

Wasnā€™t brute-force intended? My simple brute force solution got AC.

http://www.codechef.com/viewsolution/3179852

I had an analysis as to why it should get AC, but I fear its too vague
and not specific.

I always thought that setter/tester is watching submitted solutions (not all of course) and adds some tests, when he sees, that there are solution not intended to be acceptedā€¦

Bruteforced it tooā€¦
But started with removing 1-degree vertices as @m_a_y_a

I used exactly the same approach as @ddhruvkr and got AC. And this algo is giving correct answer on both the test cases mentioned aboveā€¦
Can anyone think of a test case where this algorithm fails??

It is hard to monitor the submissions all the time. And also there are a lot of creative but wrong algorithms. Your understanding will be appreciated.

@shangjingbo can you tell me how to construct the Tutte matrix for a given graph. If you say it is random then for the same two graphs matrix can be same. how do you resolve that ??. Thanks.