Read the wiki, and Xij = rand(), Xji = - Xij. if i < j and (i, j) is an edge.
What do you mean by âDue to the randomness, we can solve this problem with a high probabilityâ âŚand also How to find determinant of matrix using gaussian elimination??Please tell.
@herman, if you perform the classic gaussian elimination, and if you put the matrix in Upper Triangular form, then, the determinant is simply the product of its diagonal.
@jaggi1234 & @ddhruvkr, iâm not sure if your assumption is correct but Iâm pretty sure that itâll fail in this case , Refer to the image and Iâm sorry for the bad image 
Your Algo will remove the edge circled in blue , which disconnects the graph and itâll result in a âNOâ, but the answer is âYESâ !
If this case was included you both shouldâve got WA be glad you got AC 
Cheers !!
2 Likes
@m_a_y_a, Iâve followed an algorithm similar to yours, except that when i encounter a cycle i do the following :
â> Check if the cycle has an articulation point,
â> If yes, then retain only the edge connecting the articulation point to ODD no of vertices and remove the other edges (if multiple edges with odd vertices are there , then select any one ) and then continue with your algorithm again,
â> If no, then just check how many vertices are there, if even then âYESâ if odd then âNOâ.
Thats pretty much it
1 Like
Hi! I also used Havel-Hakimi theorem but also got WA⌠Used same idea as you did
The randomness means Xij should be chosen randomly
First Things FIRST:
-
Interesting problem (though a ready-made algorithm was available).
-
Good that the problem statement did not mention any unwanted stuff like (no ODD cycles and all), else it would have been simple bi-partate matching.
-
Tutte Matrix was a really interesting method.
Issues:
-
I was on this problem for many days, trying to implement blossomâs algo flawlessly (Couldnât succeed though). And eventually many brute-force and normal BP-Matching solutions passed, definitely due to lack of proper cases not because their algo is apt.
-
Shangjingboâs comment which says they couldnât monitor all the solutions, wasnât convincing. So if you can neither design proper cases, nor monitor solutions which get accepted with flaws, why frame a problem ? That was disappointing due to improper testing.
4 Likes
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;
}
i canât understand ,what your code is doingâŚ(itâs unformatted) ⌠please edit it so that itâd be readableâŚ