Fill The Matrix Bfs Approach

general
, ,
1

i have applied bfs in my code i am traversing level order and assigning value to node and then if i found anything contradicting then answer that no.please help with my solution https://www.codechef.com/viewsolution/15369875

2

used same , see if you checked contradictions correctly read this

3

This is what I was doing at first!!

You missed a vital point while assigning the values to the nodes.

The problem statement states that: A matrix B (consisting of integers) of dimension N × N is said to be good if there exists an array A (consisting of integers) such that B[i][j] = |A[i] - A[j]|, where |x| denotes absolute value of integer x.

Consider one of the m queries to be: 1 2 1

What your code does is initialize node 1 with 1 and node 2 with “value of node 1 + 1”.

So, val[1] contains 1 and val[2] contains 2. Is this correct?

No, its partially correct!

If you assign val[1] with 1, then val[2] can be both 2 as well as 0 ( the problem statement clearly mentions integers).

If val[2] = 0, then |val[1] - val[2]| = 1.

If val[2] = 2, then |val[1] - val[2]| = 1.

You filled a single slot in the value array(val[]) in just one way while there were two possible ways to fill a single slot in val[]. This mistake compounded as the number of queries increased.

How to get AC then??

There’s just a bit of change that needs to be done with your code.

You fill val[] the same as you are doing now. But instead of,

 if(abs(val[x]-val[v[x][y].first])!=v[x][y].second)

do this,

 if(abs((val[x]-val[v[x][y].first])-v[x][y].second) % 2 != 0)

Since, we can fill a single slot in two ways (but we are just doing it in one way), the difference should be either 0(this case arises if the test case was for a matrix which was filled as the way we are doing i.e. adding 1) or a multiple of 2 (this case arises if the test case was for matrix which has some of its cells filled in the other way i.e. subtracting 1).

Hope this clears your doubts. If you face any further problems, just leave a comment.

Here’s my wrong solution (this used the same logic as yours) -> https://www.codechef.com/viewsolution/15241113

Here’s my accepted solution (this kept the possibility of filling the val[] in two ways into account, by adding the modulo 2 check) -> https://www.codechef.com/viewsolution/15241951

You also need to check for one more case.

Consider one of the m queries to be 2 2 1. Clearly, this is not possible. Your code misses a check for such cases. Add this too.

P.S. I have not submitted your code but I think that this two changes can get you an AC.

Good luck!