Fillmtr wa

general
, ,
1

So I’ve failed to come up with a testcase of fill the matrix for which my code fails. I have got correct only for the 2nd subtask. The logic I have used is, if a cycle is found and the no. of 1’s in the cycle is odd, answer is “no” else the answer is yes.

Here is my code- Solution: 15330674 | CodeChef

I want to know a testcase for which my solution fails. Thanks in advance.

2

Well,

You may refer to my explanation for this problem here and here…
and my code here…

Hope this helps…

Please upvote if you find this helpful…

1 Like
3

Well if you can give a failing test case, it would be great. Thanks anyway

4

Well, I dont’t understand your code as im not familiar with C language, but if you explain what your code do, i might be able to help, might be able to find test cases for which your code may fail…

5

Case 1: If i=j and val=1, print “no”
Case 2: If i and j already has a val, and if a different val with same i and j is inputted, print “no”
Case 3: If b[i][j]!=b[j][i], print “no”
Case 4: If any cycle(s) is found and no. of 1’s is odd in the cycle, print “no”

Print yes for other cases

This is what my code does, and only 1 test case passes

6

Well,

You have handled the corner cases really well, After that, instead of going for finding circles in graph, you can make your life easier…

You know, by going for vertex coloring, coloring endpoints of an edge with same color if edge val == 0 and different color if val == 1

This way, if you find any contradiction, ans is no
else ans is yes…

I have explained this solution in detail in above links…

Accept answer (just joking) if this helps :stuck_out_tongue: :smiley:

7

Try this as a test case

1
4 5
1 2 0
1 3 1
1 4 0
2 3 1
3 4 0

Correct answer is “no”, but your code is returning “yes”

The first problem in your code is

d[f]=d+dis-d[f];
if(d[f]%2==1)
{
    c=1;return;
}

d[f] is declared as “int”, so may be negative. The remainder operation can have a result of “-1”. You need something like

if (d[f]%2 != 0) { ... }

Second problem is that changing the d[f] array is wrong. You need to say

if ((d+dis-d[f])%2 != 0) { ... }

With those two changes, the code might be logically correct, but too slow to pass.

1 Like