You are not logged in. Please login at www.codechef.com to post your questions!

×

FILLMTR - Editorial

0
2

PROBLEM LINK:

Practice

Contest

Author: Praveen Dhinwa

Tester: Jingbo Shang

Editorialist: Hanlin Ren

DIFFICULTY:

Easy-Medium

PREREQUISITES:

disjoint set union, bipartite graph, spanning forest

PROBLEM:

A matrix $B_{N\times N}$ is good if there is an array $A$ such that $B_{i,j}=B_{j,i}=|A_i-A_j|$ for all $1\le i,j\le N$. Given a matrix where exactly $Q$ entries are filled, and every filled entry is $0$ or $1$, determine if we can fill the rest entries(by any integer, possibly not $0,1$) such that the resulting matrix is good.

QUICK EXPLANATION:

The answer is "yes" if and only if you can assign every number in $[1,n]$ even or odd, such that:

  • When $B_{i,j}=0$, $i$ and $j$ have the same label;
  • When $B_{i,j}=1$, $i$ and $j$ have different label.

To check this, we can either:

  • Link a bidirectional edge $(i,j)$ for any known $B_{i,j}$, find a spanning forest and assign labels along the tree greedily, and check if the assignment is valid;
  • or, use a Disjoint Set Union structure that maintains parity information, and add edges into the structure.

EXPLANATION:

An observation

The problem actually asks if there exists an array $A$ that satisfies $Q$ conditions of the form "$|A_i-A_j|=val$". Consider a graph with $n$ nodes, for every such condition, we link an edge with weight $val$ between node $i$ and node $j$.

Let's say a node $i$ is even if $A_i\equiv 0\pmod 2$, otherwise say node $i$ is odd. Then,

  • if two nodes are connected by an edge of weight $0$, then they're both even or both odd;
  • if two nodes are connected by an edge of weight $1$, then one of them is even and the other is odd.

Thus, if the array $A$ exists, there must be an assignment that maps every node to either even or odd, and satisfies the above requirements. But can the existence of $A$ be guaranteed by the existence of that assignment? The answer turns out to be yes! For a valid assignment, we simply put $A_i=1$ if node $i$ is odd, and put $A_i=0$ if it's even. Why does this work? For every edge $(i,j)$ in the graph,

  • if its weight is $0$, then either $i,j$ are both odd, or they are both even. If they are both odd, then $A_i=A_j=1$; if they are both even, then $A_i=A_j=0$. In both cases we have $A_i=A_j$;
  • if its weight is $1$, then one of $A_i,A_j$ is $1$ and the other is $0$, therefore $|A_i-A_j|=1$.

We see that all edges, no matter its weight is $0$ or $1$, is satisfied by our array $A$.

That is to say, the answer is "Yes" if and only if there exists a valid assignment. How to check this? There are many different solutions:

Author's Solution

Let's first find a spanning forest of the graph. We can maintain a data structure called disjoint set union("DSU"), and do something similar to Kruskal's Algorithm.

As in Kruskal's Algorithm, initially no edge is added to the graph, and every vertex itself forms a set. Then let's add edges one by one, in an arbitrary order(since we only need "a spanning forest", not a "minimum" one or something, so any order is acceptable). Every time we add an edge $(u,v)$, if $u$ and $v$ are in different sets, we combine these sets into one set, and add this edge to the spanning forest; otherwise we do nothing.

Pseudocode:

for i in nodes makeset(i) //i itself is a set for (u,v) in edges if find(u) != find(v) add edge (u,v) to the edge list of spanning forest Union(u,v)//merge two sets

After we have a spanning forest, we can solve the problem. First let's consider the case that all edges are in the spanning forest. In this case the answer is always "Yes", and we can find a valid assignment in linear time. For every connected component, we pick an arbitrary node $v$ and suppose $v$ is even. For any node $u$ in this component, if the distance between $u$ and $v$ is odd(i.e., there are odd edges that has weight $1$ in the path from $u$ to $v$), then $u$ is odd; otherwise $u$ is even. This assignment can be computed in one dfs:

dfs(u) : //procedure dfs() for v is u's child : parity[v] = parity[u] xor (the weight between (u, v)) dfs(v) //main for i in nodes : if i's component is not visited : dfs(i)

What if there are other edges? Note that no "other edge" can cross two components. If for every edge $(u,v)$, (the parity of $u$) xor (the parity of $v$) xor (the weight of $(u,v)$) is $0$("parity constraint"), then the assignment is already valid. Otherwise, say edge $(u,v)$ violates that constraint, then there is a cycle of odd weight(that passes through $u$ and $v$). A cycle of odd weight means that a number's parity is different from itself's, which is impossible. So we only need to check if every other edge satisfies the parity constraint.

To demonstrate the idea, let's consider the last test case in the sample. A spanning forest(tree) is shown below. Now we are adding an edge $(1,3)$ which has weight $1$. However parity of $1$ and $3$ are both $0$(even), and this edge has weight $1$, thus violates the parity constraint. Since there is an edge that violates the constraint, there should be an odd cycle --- it's $1\to 2\to 3\to 1$ in this case, and this cycle means that $parity(1)\ne parity(1)$, so there must be no solution.

sample

Pseudocode:

for (u, v) in edges : if parity[u] xor parity[v] xor weight[u,v] == 1 : //an odd cycle found print "No" and exit print "Yes"//All edges satisfy the parity constraint

The time complexity is $O(M\alpha(N))$, since we used DSU.

Tester's solution

We can modify the DSU structure so that it records parity information. Recall that the DSU structure is a set of rooted trees, where a tree stands for a set. Let father[x] be $x$'s parent.

The basic procedure for DSU is finding root. Let find(x) be $x$'s root. We'll use a technique that's called path compression: for every node that lies between $x$ ans $find(x)$, we set its father to be the root. The following is a demonstration of path compression.

path compression

Pseudocode:

find(x) : if x == father[x] : //x is root return x father[x] = find(father[x]) //path compression return father[x]

When merging two sets, we set the father of one's root the other root:

Union(x, y) : father[find(x)] = find(y)

Now comes the modification: for every node $x$ in the DSU, we maintain diff[x], which is defined as parity(x) xor parity(father[x]). For example, consider the DSU shown in picture below. Black/white nodes are odd/even nodes respectively, and the value of diff[x] is written on the edge $x\to father[x]$. Note that find() changes several diff's(red ones).

diff

We can easily rewrite our find() function. Let parity(x) be x's parity($0$ if x is even and $1$ if x is odd). In the following code, $t$ is $x$'s original father, and after find(t), diff[t] becomes parity(root) xor parity(t). Now the old diff[x] is equal to parity(x) xor parity(t), and we want the new diff[x] become parity(root) xor parity(x). It's easy to see diff[x](new) should become diff[x](old) xor diff[t].

find(x) : if x == father[x] : return x t = father[x] //the original father of x father[x] = find(t) diff[x] = diff[x] xor diff[t]//compute new diff[x]. return father[x]

When merging two sets, we not only set the father of root_x be root_y, but also computes the new diff[root_x]. In the following pseudocode, w is the weight of inserted edge so parity(x) xor parity(y)=w; We also have parity(x) xor parity(root_x)=diff[x] and parity(y) xor parity(root_y)=diff[y]. Thus diff[root_x], which should be equal to parity(root_x) xor parity(root_y), can be computed by w xor diff[x] xor diff[y].

Union(x, y, w) : //w is the weight of the edge (x, y) root_x = find(x) root_y = find(y) father[root_x] = root_y diff[root_x] = w xor diff[x] xor diff[y]//compute diff[root_x].

OK, with the modified DSU structure, we can solve the problem more conveniently. Just like Kruskal's algorithm, we insert edges one by one. For an edge $(u,v)$ with weight $w$, if $u$ and $v$ are in different sets, we just merge them; if they are in the same set, we use diff to check if this edge doesn't make an odd-weighted cycle. The indicator for an odd-weighted cycle is an edge (x,y) with weight w such that parity(u) xor parity(v) xor w=1. Since u and v are connected, they have the same root, say r. Then diff[u]=parity(r) xor parity(u) and diff[v]=parity(r) xor parity(v), so what we need to check is diff[u] xor diff[v] xor w=1.

for (u,v) in edges: w = weight of (u,v) if find(u) != find(v) : Union(u, v, w) else : if diff[u] xor diff[v] xor w == 1 : return "No" //otherwise do nothing

So we just scan all edges and judge every edge that's not in the forest one by one. This solution also has complexity $O(M\alpha(N))$.

Editorialist's solution

We can find a spanning forest by simple dfs.

Let's iterate over all nodes. When we meet an unvisited node, we mark it as visited, search its component, and return the dfs tree. Of course, every node in its component is also marked visited. When we meet a visited node, we just do nothing. The procedure is better described by pseudocode:

dfs(x) : visited[x] = true for y adjacent to x if not visited[y] then add (x,y) to the spanning forest dfs(y) construct_spanning_forest() : for i in all nodes if not visited[i] then dfs(i)

This gives the spanning forest in linear time. The rest is the same as Setter's solution.

A note on DSU's complexity

There are two tricks that used in DSU to make its complexity $O(\alpha(n))$ per operation.

The first one is path compression, which we mentioned in Tester's solution part. The second one is union by rank, which means: when you merge two sets rooted at $r_1$ and $r_2$, you should let the final root be the one whose rank is larger; and the rank is something similar to depth. You can find detailed explanation here.

If you only use path compression, or you only use union by rank, the complexity should be $O(\log n)$ per operation. The implementation in this editorial only uses path compression, so its complexity is actually $O(M\log N)$.

However, in practice, people usually only implements path compression. The reason is that for most cases, path compression performs already quite fast. In fact, as pointed by the Author, the complexity of path compression with randomized union is $O(\alpha(n))$ per operation, and many data can be seen as random data for DSU. See this paper for more details.

ALTERNATIVE SOLUTION:

As you can see, there are many approaches to tackle the problem.

So if your solution is different with ours, feel free to leave a comment :D

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.(NOTE: This gets WA)
Tester's solution can be found here.
Editorialist's solution can be found here.

RELATED PROBLEMS:

This question is marked "community wiki".

asked 24 Aug, 17:34

r_64's gravatar image

7★r_64
260410
accept rate: 20%

edited 11 Sep, 17:08

admin's gravatar image

0★admin ♦♦
17.4k347486515

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

(25 Aug, 04:49) dpraveen ♦♦4★

@dpraveen Thanks! Added to the editorial.

(25 Aug, 08:18) r_647★

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.

(12 Sep, 18:48) rachitiitr6★

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

Codechef SEPT17- FIll the Matrix

Cheers!

link

answered 12 Sep, 03:14

gkcs's gravatar image

4★gkcs
2.5k11025
accept rate: 9%

I have used graph node coloring to solve this problem.

Firstly i checked for self loops and then for edge from u to v when an edge from v to u is already given, thus adding a bidirectional edge in a graph only once.

In case of self loop, if val == 1, ans is no. in case of edges where edge between same vertices but opposite direction is already given, if val of both edges is different, ans is no.

after that, run a dfs on all unvisited vertices, coloring them with same color as their parent if val ==0 and different color if val==1. if found any contradiction during color assignment, ans is no.

If given graph pass all these tests, ans is yes....

PS: i found editorial solution a way too complex, so i posted mine.

Feel free to ask anything. Please upvote if you found this helpful.

Here's a link to my Code

link

answered 11 Sep, 16:09

taran_1407's gravatar image

5★taran_1407
2.0k418
accept rate: 22%

Isn't this the same as editorialist's solution?
Although I agree that the editorial makes the problem seem way more complex that it is.

(11 Sep, 16:14) meooow ♦5★
4

Facepalm... This problem has so many solutions and Editorialists should describe all them in details...

(11 Sep, 16:25) r_647★

Editorialist's solution is what I majorly followed :p . But I must say, I learnt a lot of terminologies from editorial. Reminds me that I still have a long way to go...:)

(11 Sep, 16:31) vijju123 ♦4★
1

@r_64 just my opinion :P
Although you do explain things in considerable detail, which I'm sure I will appreciate when going through the WEASELSC editorial

(11 Sep, 16:47) meooow ♦5★
1

Well, to say the truth, i didn't even read the solution line to line but only after seeing the PREREQUISITES, it was apparent to me that the solution discussed here would appear far more complex than it actually is!!! Which, i believe, is never appreciable.

@meooow my solution resembles the editorial one considerably, but not in finer details as well as complexity as i think.

(11 Sep, 18:14) taran_14075★

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.

link

answered 11 Sep, 16:12

hemanth_1's gravatar image

6★hemanth_1
7908
accept rate: 20%

PLEASE ELABORATE. thanks

(12 Sep, 11:35) goyal_banna3★

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 a1 with 0 and a[3]=a1XOR 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. Code

link

answered 11 Sep, 19:18

stranger7's gravatar image

5★stranger7
1214
accept rate: 25%

The testcases for this problem were very weak. My solution 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.

link

answered 11 Sep, 19:39

sherewillpower's gravatar image

5★sherewillpower
293
accept rate: 0%

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.

link

answered 12 Sep, 18:41

rachitiitr's gravatar image

6★rachitiitr
1.4k317
accept rate: 0%

edited 12 Sep, 18:42

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: CODE

link

answered 11 Sep, 16:50

shubham_raj199's gravatar image

4★shubham_raj199
321
accept rate: 0%

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

link

answered 11 Sep, 22:15

shivam_07's gravatar image

4★shivam_07
1
accept rate: 0%

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.

link

answered 11 Sep, 23:34

rp789's gravatar image

4★rp789
22
accept rate: 0%

edited 11 Sep, 23:43

Can you tell some test cases where it may fail.

(11 Sep, 23:44) rp7894★

It didn't actually work :-(.

(11 Sep, 23:48) rp7894★
1

You only considered cycles of length <= 3. Try this:

1

5 5

1 2 1

2 3 0

3 4 1

4 5 0

5 1 1

(12 Sep, 06:38) r_647★

The problem is not yet added to the practice portal

link

answered 12 Sep, 18:04

rohitthapliyal's gravatar image

4★rohitthapliyal
534
accept rate: 0%

It is already added dear.

(12 Sep, 18:23) vijju123 ♦4★

Yeah, but was not visible at that moment. Fixed now.

(13 Sep, 00:12) rohitthapliyal4★

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

link

answered 12 Sep, 18:41

jain_0709's gravatar image

4★jain_0709
1
accept rate: 0%

I have used the same approach

Explanation https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997

A link to code is given alongwith..

Feel free to ask anything... Upvote...

(13 Sep, 14:52) taran_14075★

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 : CODE

link

answered 13 Sep, 00:14

rohitthapliyal's gravatar image

4★rohitthapliyal
534
accept rate: 0%

@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

link

answered 13 Sep, 17:32

iprakhar22's gravatar image

3★iprakhar22
31
accept rate: 0%

` cananyone tell me why my logic isnt working
#include <cstdlib> #include<iostream> 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;

link

answered 13 Sep, 21:54

satya753's gravatar image

1★satya753
11
accept rate: 0%

edited 14 Sep, 07:06

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 ....

link

answered 14 Sep, 00:51

namitp's gravatar image

4★namitp
1
accept rate: 0%

Well, You ought to go for vertex 2-coloring instead of bipartite graph testing...

You might like to have a look at my approach with explanation

https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997

Feel free to ask anything...

Please upvote

(14 Sep, 23:13) taran_14075★

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

link

answered 14 Sep, 19:04

durden8055's gravatar image

4★durden8055
1
accept rate: 0%

Well, i dont code in C language, so i can't understand your code...

But, You might like to have a look at my approach with explanation

https://discuss.codechef.com/questions/109357/fillmtr-editorial/110997

Feel free to ask anything...

Please upvote...

(14 Sep, 23:14) taran_14075★

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.
link

answered 17 Sep, 18:21

akash_321's gravatar image

3★akash_321
242
accept rate: 0%

edited 17 Sep, 18:23

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.

link

answered 26 Sep, 18:03

mayank_kool's gravatar image

3★mayank_kool
1
accept rate: 0%

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.

link

answered 03 Oct, 13:11

divay95's gravatar image

2★divay95
11
accept rate: 0%

edited 03 Oct, 15:09

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,081
×283
×67
×23

question asked: 24 Aug, 17:34

question was seen: 3,825 times

last updated: 03 Oct, 15:09