FILLMTR - Editorial

This problem can be converted to 2-SAT, just add (i XOR j) if B[i][j]=1 or, (i XNOR j) if B[i][j]=0, to the implication graph.

1 Like

I used BFS.
Observations: Check whether the given entries of matrix do not conflict with each other?
How can we check that?
Assume some values and just explore all the values that are affected by that assumed value,and if any conflict is there return NO otherwise YES
So What we do?
We are given some graphs ,in which we may have several components in each component assume one node’s value and derive the values of other nodes in the component ,if any conflict is there return NO otherwise YES .
Code:


[1]


  [1]: https://www.codechef.com/viewsolution/15236840

There can be a really easy greedy solution the problem.We can initialise the array A by -1.There is crucial observation that the array A can be constructed with only two values 0 and 1.Sort the index value pairs.Now if both the given index are unassigned,assign them according to the value given.Like 1 3 1 would mean 1 and 3 would be different .So initialise a[1] with 0 and a[3]=a[1]XOR val.Keep doing this and if at some point when both the indices are intialised with values!= -1 ,then check if they satisfy the given value,if not break and print -1.


[1]


  [1]: http://www.codechef.com/viewsolution/15278044
2 Likes

The testcases for this problem were very weak.
[My solution][1] got an AC even though it is incorrect. It is easy to see that this fails in cases where 2 previously visited sets of weight 0 have an edge of weight 1 in between.
An example where my solution should fail is :
1
5 4
1 2 0
1 5 0
3 4 0
4 5 1
I reported the issue in the comments section of the problem link but to no avail. I wonder how many people with a similar solution got away with an AC.
[1]: CodeChef: Practical coding for everyone

1 Like

Test cases are weak My solution is getting 100 marks even though i get wrong answer for the test cases i made.

What I thought is we can see for the conditions when the array is not possible.
There would be 3 cases for this:

  1. For an index (i, j) of the matrix a, if (i==j) but a(i, j) =1.

  2. For two different indices (i1, j1) and (i2, j2) if(i1=j2) and (i2=j1) but a(i1, j1)! =a(i2, j2).

  3. For three different indices if any two of them have one common index (i, j) then the number of 1’s at these three indices should not be 1 or 3. Eg. If three indices are (1,2), (1,4), (2,4) here for any two indices 1 index(i or j) is common. Then for this 1 should not be at all the three positions or there should not be only one 1 at any of these 3 indices.

Can you tell me if there is any problem with this logic.

Hi everyone!
This editorial is great, but I made a video editorial on this problem anyways :slight_smile:
It talks about using disjoint sets to solve this:

Codechef SEPT17- FIll the Matrix

Cheers!

7 Likes

The problem is not yet added to the practice portal

I tried to solve it using bicoloring(dfs) but getting TLE on subtask 2 of task 2. Can someone help me ? Here is my code:
https://www.codechef.com/viewsolution/15367330

The editorial seems actually very long. But its good as it is detailed.
I have summarized the tutorial in my short ~10 min video here : https://www.youtube.com/watch?v=6qWg7-O4Fmg

You can refer this for complete list of video tutorials for SEP17 including WEASTELX.

1 Like

I used bipartite graph for 1 difference edges and disjoint sets for 0 difference edges. I am getting WA. Please, take a look at the code :


[1]


  [1]: https://www.codechef.com/viewsolution/15414051

@taran_1407
Sorry I don’t know how to reply to your comment.
I used the same approach. Can you find out why my code is getting TLE in the 2nd task of the 2nd subtask ?

[My Code][1]
[1]: CodeChef: Practical coding for everyone

` cananyone tell me why my logic isnt working
#include
#include
using namespace std;

        /*
         * 
         */
        const int MAX=2e6+9;
        int main() {
            int i  ,t ,n ,q;
            cin>>t;
            while(t--){
                cin>>n>>q;
                int v[MAX]={0} ,x ,y ,d , a[MAX]={0};
                for(i=1;i<=n;i++){
                    a[i]=0;
                    v[i]=0;
                }
               int f=0;
                while(q--){
                    cin>>x>>y>>d;
                    if(x==y){
                        if(d!=0){
                            f=1;
                        }
                        v[x]=1;
                        a[x]=0;
                        
                    }
                    else  if(v[x]==0&&v[y]==0){
                  
                        a[x]=0;
                        a[y]=d+a[x];
                        v[x]=1;
                        v[y]=1;
                    }
                    else  if(v[x]==0&&v[y]==1){
                        a[x]=a[y]+d;
                        v[x]=1;
                    }
                    else  if(v[x]==1&&v[y]==0){
                        a[y]=a[x]+d;
                        v[y]=1;
                    }
                    else  if(v[x]==1&&v[y]==1){
                        if(abs(a[x]-a[y])!=d){
                            f=1;
                        }
                    }
                }
                if(f==1){
                    cout<<"no"<<"\n";
                }
                
                else{
                    cout<<"yes"<<"\n";
                }
                
            }
            
        }
         
           `can anyone tell me why my logic is not working 

first i declared two array a[] and other array v[] array v will keep the record of all the integers which
are visited now during each query 4 condition arises

  1. both 1st and 2nd are unvisited
  2. 1st is visited and 2nd is unvisited
    3 1st is unvisited and 2nd is visited
    4 both are visited
    now
    for the 1st condition
    i marked both the nodes as visited
    and assigned a[i]=d;
    a[j]=a[i]+d;
    for the 2nd condition
    marked 2nd node as visited
    a[j]=a[i]+d;
    for 3rd condition
    marked 1st node as visited
    a[i]=a[j]+d;
    for 4 th condition
    since both nodes are visited and are assigned some values
    therefore
    if(abs(a[i]-a[j])!=d)
    ans=no and exit
    else
    ans=yes;

Will anyone please tell me whats the problem with my solution …
Thnks in advance…

i tried checking if graph is bipartite or not…
https://www.ideone.com/OGDY8I

PLease do check …

can anyone give me test case where my code fails ?
here is the link - https://www.codechef.com/viewsolution/15423175

can anyone tell me what is wrong in this logic

  1. Initially all nodes are uncolored.
  2. As I get values of i,j and val, if both a[i] and a[j] are uncolored then if val is 0 then give them same color or if val is 1 then give different colors.
  3. If anyone of a[j] or a[i] is already colored then color other one accordingly if val is 1 then different color or same color if val is 0.
  4. If both a[i] and a[j] are colored then if val is 0 then they should have same color if not then matrix is wrong similarly if val is 1 then they should have different color if not the matrix is wrong.
  5. In all other cases matrix will be correct.

Hello! can anyone pls tell me why the solution on going according to author’s logic is getting WA? I have written code according to the logic explained in the “Author’s Solution” section of the editorial which seems to be absolutely correct. Any help is much appreciated. Thanks!! U can find my code here.

Simple solution can found only by sorting the initial m commands and then trying to assign the values to the array. This takes O( m*log(m) ) time, which is the time for sorting. U can see the solution here.

This paper proves that you can, in fact, use randomized union rather than union by rank, and will still get same amortized time complexity.

@dpraveen Thanks! Added to the editorial.