FILLMTR - Logic fail ?

In FILLMTR , I used the following approach :
Make a graph with 0 or 1 as the edge-weight. Check if the graph contains a cycle which has odd number of vertices and odd number of one’s in weights of the path of the cycle. If found such cycle, ans is no, else yes. Checked for the corner cases for B[i,i] cant be 1 and B[i,j] cant have duplicate values with different weights.
My Code

I got WA and TLE in the 1st and the 2nd sub-tasks.
Can you tell me where does my logic fail or if my code has any errors ?

Well, your logic is correct in theory but in practice, you can make your life easier by using two facts which you already know.

First thing, self edge B[i,i], don’t add it to adjacency list…

just as you are taking input, add a simple check
if src == dest vertex
if(val != 0)ans = “no”;

No need to check even for cycles in this case…

Second thing, whenever you input an edge from src vertex to dest vertex, check if there already exist an edge from dest to src vetrex.

if yes

If val1 != val2 ans = “no”, no need to check for odd cycles.

else do nothing… don’t even add this edge to graph.

else

add an undirected edge from src to dest in graph with edge weight val.

Now, all the corner cases we have already covered.

Now, run a dfs on graph, coloring vertex, with same color if edge weight between them is 0.

If edge weight is different, color with opposite color…

If 2-coloring not possible ans = “no”
else ans = “yes”…

You may have a look at my code Here

I have also added a similar explanation Here

Please upvote if you find this helpful…

1 Like

Thank you so much. :slight_smile:
Would have definitely upvoted if i had enough karma or whatever the rules are of codechef discuss section

1 Like

Well, i too need karmas :stuck_out_tongue:

I can use some more as well :stuck_out_tongue:

I didn’t get you @vijju123

By the way, @iprakhar22, you definitely can upvote as i know…