SEAGRP wrong answer

general
1

I am getting wrong answer for following question.

Sereja has undirected graph, which consists of n vertexes and m edges. Sereja can delete edges from the graph. Now Sereja is interested in one question : is it possible to delete edges in the graph so that the degree of each vertex in the graph will be equal 1?
Please, help Sereja.

problem link
Approach:: we have to check whether there is perfect matching or not. i have solved it using tutte’s matrix calculate determinant of matrix using gauusian elimination if determinant is greater then 0 then then print YES otherwise NO.

Code link here

please tell me if i am doing something wrong.

1 Like
2

Hi,

take a look at this solution. The author mentioned that he recalculated the determinant multiple times. I am also stuck on this problem, here is my tutte/gaussian approach.

3

I have edited my code and calculate determinant 10 times but it also giving wrong answer

edited


[1]


  [1]: http://ideone.com/4J1UC0
1 Like
4

Here link to my code- http://discuss.codechef.com/questions/35358/seagrp-editorial
I was rather stuck at working of gauss elimination and so have commented that section particularly.
We find the determinant multiple times because the Tutte Matrix method is probabilistic since the matrix values are filled randomly (over a large set ) and hence running the loop assures that the chance or WA are minimal!
Hope it helps. Other resources-
Seagrp Editorial- Codechef
Wikipedia- Gaussian Elimination / Tutte Matrix

Cheers