mohitbindal's blog

By mohitbindal, history, 8 years ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 .

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for showing your interest, actually I figured the silly mistake I did.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by mohitbindal (previous revision, new revision, compare).