I checked my solution of Chef and Bipartite Graphs against many randomly generated test cases using below attached files and the solution seems correct, but codechef judge is giving WA for the particular solution even after rejudge. Can anybody please help me to figure out the problem with my code, or the checker.
Question Link : https://www.codechef.com/ACMIND16/problems/ICPC16F
Solution Link : http://ideone.com/nV20zD
Random Input Generator Link : http://ideone.com/lZZlbt
Checker Link : http://ideone.com/wm8EzY
Update : I found my mistake.
Can you please explain your approach . Our approach was quite similar to yours , but we took care of the pairing in such a way that the 2 nodes that we connect each time is not connected before .
My logic is something like this. I am using InL[] array to store the degree of the vertices on the left side and inR[] for the right side, vis[][] array to store whether an edge from i to j (i being a vertex in left part and j in the right part) is already present or not (i.e to make sure an edge is not added twice between same pair of vertices).
At first I am assigning (m / n) no of edges from each vertex. For the left side vertices I am moving sequentially from 1 to n and assigning (m / n) no of edges to each, and for the right side of vertices I am using a priority queue (sorted in assending order according to degree of the right side vertices) to assign an edge to the vertex with minimum degree.
Similarly I am assigning the remaining edges (i.e m % n edges) using the above method.
Thanks for showing your interest, actually I figured the silly mistake I did.
What was your mistake ?
What was it?
I did a very silly mistake, In line 84 of my code I used inR[i] but that was supposed to be inR[cur.ss].
Auto comment: topic has been updated by mohitbindal (previous revision, new revision, compare).