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

×

PARITREE - Editorial

PROBLEM LINK:

Contest
Practice

Authors: Praveen Dhinwa and Malvika Raj Joshi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

DIFFICULTY:

Medium

PREREQUISITES:

XOR, disjoint set union, graph traversal, bicoloring

PROBLEM:

You are given an $N$-node tree, and you need to assign weights to the edges. The weight of each edge can be $0$ or $1$, but they must satisfy $Q$ conditions of the following kind:

  • Given $(u,v,x)$, the sum of the weights of all edges from $u$ to $v$ must have parity equal to $x$.

How many assignments of edge weights are there, modulo $10^9 + 7$?

QUICK EXPLANATION:

Root the tree on any node (say $1$), and for every node $i$, let $x_i$ be the XOR of all edge weights from root to $i$. Then the condition $(u,v,x)$ is satisfied if and only if $x_u \oplus x_v = x$, so we only need to count the assignments of the $x_i$s.

Create a new graph with $N$ nodes, and add an edge from $u$ to $v$ with weight $x$ for every condition $(u,v,x)$. If this graph contains a cycle with odd total weight (which can be found with bicoloring), the answer is $0$. Otherwise, if this graph contains $K$ components, then the answer is $2^{K-1} \bmod (10^9 + 7)$.

EXPLANATION:

In this explanation, we will go straight into the solution for the final subtask, and simply note that the first subtask can be solved by trying all $2^{N-1}$ assignments of weights to the $N-1$ edges (which runs in $O(N^2 2^N)$ time).

First, the conditions seem quite complicated because each condition gives a restriction among weights of edges along some path, so potentially a lot of edges are affected per condition. As with any problem involving unrooted trees, it usually helps to root the tree first. Since we don't know any better yet, let's try rooting the tree at an arbitrary node, say at node $1$.

When the tree is rooted, we can view a path as consisting of two parts, an upward path and a downward path. (One or both parts may consist of zero edges.) Specifically, consider the path from $u$ to $v$. Let $w$ be the lowest common ancestor of $u$ and $v$. Then the path from $u$ to $v$ consists of the path from $u$ to $w$ (the upward path) and the path from $w$ to $v$ (the downward path). The XOR of the weights of the edges from $u$ to $v$ is simply the XOR of the following two values:

  • The XOR of the weights of edges from $u$ to $w$.
  • The XOR of the weights of edges from $v$ to $w$. (Note that the order doesn't matter because XOR is commutative and associative.)

We can modify this slightly. Since every number is its own XOR-inverse, we can also say that the XOR of the weights of the edges from $u$ to $v$ is the XOR of the following two values:

  • The XOR of the weights of edges from $u$ to $1$.
  • The XOR of the weights of edges from $v$ to $1$.

This formulation counts the edge weights from $w$ to $1$ twice, which means they don't affect the XOR. (Every number is its own XOR-inverse, which means these weights will cancel out in the XOR.) This gives us a possible alternative interpretation of the conditions: Define $N$ new variables $x_1, x_2, x_3, \ldots, x_N$, one for every node. Define $x_i$ to be the XOR of the edge weights from $i$ to $1$. Then the condition $(u,v,x)$ is satisfied if and only if $x_u \oplus x_v = x$. (Here $\oplus$ denotes the XOR operation.) This simplifies our conditions down to a simple relationship between two variables, $x_u$ and $x_v$!

So our strategy now is to instead count the number of assignments of the $x_i$s. But for this strategy to work, we need to show that there is a one-to-one correspondence between edge weights and the variables $x_1, x_2, \ldots, x_N$. (Actually, only $N-1$ of these are actual "variables" because $x_1$ is always $0$.) This is straightforward:

  • Any set of $N-1$ edge weights determines a unique assignment of the $x_i$ variables.
  • Similarly, any assignment of the variables $x_2, \ldots, x_N$ determines unique edge weights for all edges: namely, the edge $(i,j)$ gets the weight $x_i \oplus x_j$.

Thus, we have reduced the problem to finding the number of assignments of the variables $x_2, \ldots, x_N$ satisfying $x_u \oplus x_v = x$ for all $(u,v,x)$. In addition to being, this interpretation has another benefit: Notice that we don't actually need the tree! (In other words, the tree doesn't matter in the final answer; only the conditions.)

The most straightforward way of solving this new problem is still to try all $2^{N-1}$ possible assignments, so our goal now is to solve it more efficiently. In the following, we will describe a few such solutions (all of which are related to one another).

Solution 1

Each condition $(u,v,x)$ gives a relationship between the two variables $x_u$ and $x_v$. Our first observation is that $x$ can only be $0$ and $1$. If $x = 0$, then the statement $x_u \oplus x_v = x$ is equivalent to the statement $x_u = x_v$, and if $x = 1$, then it is equivalent to $x_u \not= x_v$.

Suppose first that $x = 0$ for all conditions. Then each condition $(u,v,x)$ says that the variables $x_u$ and $x_v$ are equal. Let's keep track of all these relationships with a new graph with $N$ nodes, where node $i$ corresponds to variable $x_i$. We add an edge $(u,v)$ for every condition $(u,v,x)$. In this graph, every two adjacent variables must be the same. This implies that all variables that belong to a connected component must be the same. Thus, in each connected component, there are only two possible assignments for all variables (because they must all be equal), except the component containing $1$ which only has one possible assignment (because $x_1$ must be $0$). So if there are $C$ connected components, then the number of assignments of variables is simply $2^{C-1}$!

Now, what if we include conditions with $x = 1$? In this case, we can still create a similar graph as above, but now we should mark each edge $(u,v)$ with $0$ or $1$, depending on the value of $x$. In this case, if an edge is marked $0$, then the variables it joins must be the same, otherwise they must be different. But again, in a connected component, selecting the value of some variable already uniquely determines the value of all other variables. (The difference is that this time, they are not necessarily all the same.) So we could also say that there are two possible assignments for each connected component (except the component containing $x_1$). But this is not true, because it may happen that the conditions are unsatisfiable!

For example, suppose we have the conditions $(10,20,1)$, $(20,30,1)$ and $(30,10,1)$. Then the nodes $x_{10}$, $x_{20}$ and $x_{30}$ belong to a connected component, but any assignment to these variables will not satisfy all conditions simultaneously! (Because we cannot find values $x_{10}$, $x_{20}$ and $x_{30}$ satisfying $x_{10} \not= x_{20}$, $x_{20} \not= x_{30}$ and $x_{30} \not= x_{10}$.) Such a thing happens because we found an "odd-weight cycle" in our graph. But finding such an odd-weight cycle is easy with a variant of graph bicoloring: No odd-weight cycle exists if and only if we can find a bicoloring of the graph such that:

  • Every pair of nodes connected by an edge marked $0$ have the same color, and
  • Every pair of nodes connected by an edge marked $1$ have different colors.

But finding such a coloring is easy and can be done with the following (assuming we're trying to color the nodes either red or blue):

  • For each connected component, color one of its nodes red, and add it to a queue.
  • Perform a BFS starting with our queue of nodes, and for each newly visited node, color it with either blue or red depending on the color of its parent and the mark of the edge.
  • Check if this assignment is valid by checking if all edge conditions are satisfied.

So now we can summarize our algorithm:

  • Ignore the given tree, and create a new graph with $N$ nodes.
  • For every condition $(u,v,x)$, add an edge $(u,v)$ marked $x$.
  • Check if an "odd-weight cycle" exists in the graph using the bicoloring algorithm above. If there is, then output $0$.
  • Otherwise, output $2^{C-1} \bmod (10^9 + 7)$, where $C$ is the number of connected components.

The new graph contains $N$ nodes and $Q$ edges, so constructing it takes $O(N+Q)$ time. Since checking for the existence of an odd-weight cycle only requires one traversal, it (and thus the whole algorithm) takes $O(N+Q)$ time!

Solution 2

You can also use union-find instead of bicoloring. This has a slightly lower complexity, but might be easier to code. This solution is inspired by this problem.

Each condition says that $x_u$ and $x_v$ are either equal or not equal. Let's introduce some new terms. Let's say that $x_u$ and $x_v$ are friends if they have the same value, and enemies if they have different values. The following are intuitive facts about friendship and enemyship:

  • If $x_a$ and $x_b$ are friends, and $x_b$ and $x_c$ are friends, then $x_a$ and $x_c$ are friends.
  • If $x_a$ and $x_b$ are enemies, and $x_b$ and $x_c$ are enemies, then $x_a$ and $x_c$ are friends.
  • If $x_a$ and $x_b$ are friends, and $x_b$ and $x_c$ are enemies, then $x_a$ and $x_c$ are enemies.

To solve the problem, we will use union-find on our $N$ variables $x_1, \ldots, x_N$, and our goal is to partition these variables so that if we know two variables $x_i$ and $x_j$ are friends, then they must belong on the same set. Initially, each variable is in their own set.

Furthermore, we will modify union-find so that each disjoint set $S$ of variables knows its enemy set $T$, which we'll define as the set of variables which are enemies of the variables in $S$. To implement this, just add a pointer for each node called enemy, and point this pointer from the representative of $S$ to the representative of $T$, and vice versa. Initially, each set doesn't have an enemy set. (Or you can add dummy enemy sets by adding $N$ new variables, which could be simpler to implement.)

Now, we will handle the conditions $(u,v,x)$ in order, and update our union-find along the way.

First, let's handle a condition $(u,v,x)$ with $x = 0$. In this case, $x_u$ and $x_v$ are friends so we want $x_u$ and $x_v$ to belong to the same set. The first step is to find the representatives of the sets containing $x_u$ and $x_v$. Then we handle a few cases:

  • If the representatives are the same, then $x_u$ and $x_v$ already belong to the same set, and nothing needs to be done.
  • If the representatives point to each other as enemy sets, then we have reached a contradiction (because $x_u$ and $x_v$ are already known enemies), so we halt the process and immediately output $0$.
  • Otherwise, we call union on $x_u$ and $x_v$. Also, we call union on the enemy sets of $x_u$ and $x_v$. Note that we must also update the enemy pointers of the two new representatives.

Handling a condition $(u,v,x)$ with $x = 1$ is similar. In this case, $x_u$ and $x_v$ are enemies so we want $x_u$ and $x_v$ to belong to a pair of sets which are enemy sets of each other. As before, the first step is to find the representatives of the sets containing $x_u$ and $x_v$. Then we handle a few cases:

  • If the representatives point to each other as enemy sets, then nothing needs to be done.
  • If the representatives are the same, then we have reached a contradiction (because $x_u$ and $x_v$ are already known friends), so we halt the process and immediately output $0$.
  • Otherwise, we call union on $x_u$ and the enemy set of $x_v$. Also, we call union on $x_v$ and the enemy set of $x_u$. Note that we must also update the enemy pointers of the two new representatives.

If the overall process succeeds without arriving at a contradiction, then we know that the conditions are satisfiable. The remaining question is how many possible assignments are there. Well, this is easy. Before we processed any condition, there were $2^{N-1}$ possible assignments. However, for every condition that gave us new information (i.e. those that made us perform union operations), we essentially entangled the fates of two sets of variables, thus reducing the number of possibilities by $2$. Thus, if there are $K$ conditions that forced us to do unions, then the answer is simply $2^{N-1-K} \bmod (10^9 + 7)$!

Solution 3

There is another solution that involves union find but is slightly different from the previous solution. Instead of placing friends in one set and their enemies in another, we place all known friends and enemies in a single set, thus removing the need for the enemy pointer. But in this version, we must remember the relationships of variables in the same set with each other. Specifically, for each node $i$, we will keep track of a bit called $D_i$, which is $1$ if $x_i$ is an enemy of its parent in the disjoint set forest, and $0$ otherwise. For simplicity, if $i$ is the representative of the set, then we say the parent of $i$ is itself, so $D_i = 0$.

As we perform union-find operations, we will need to update this $D_i$. For example, during a union operation, we need to update the $D_i$ of one of the nodes. Also, during a find operation, we will perform path compression and update the $D_i$s of all nodes in the path along the way. Note that path compression will be required in this solution.

As before, we will process the conditions $(u,v,x)$ in order and update our union-find as we go. But unlike before, the cases $x = 0$ and $x = 1$ don't need to be handled separately.

The first step is to find the representatives of $x_u$ and $x_v$. Then we will handle the following cases:

  • If the representatives are the same, then $x_u$ and $x_v$ already belong to the same set, so we only need to check if $(u,v,x)$ is satisfied. This is true if and only if $x = (D_u \oplus D_v)$. (Why?) So if this is false, we have reached a contradiction and can immediately output $0$.
  • Otherwise, the representatives are different, and we will need to perform a union operation. In this case, we will need to update the $D_i$ value of the representative of either $x_u$ or $x_v$. This new $D_i$ must be equal to $D_u \oplus D_v \oplus x$. (Why?)

If we are able to process all $Q$ conditions without arriving at a contradiction, then all that remains is to count how many possible assignments there are. But this is similar to the first solution: If there are $C$ distinct sets, then the answer is simply $2^{C-1} \bmod (10^9 + 7)$!

Time Complexity:

$O(N + Q\alpha(N))$ or $O(N + Q)$ ($\alpha$ is the inverse Ackermann function)

AUTHOR'S AND TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 13 Mar '16, 14:25

kevinsogo's gravatar image

7★kevinsogo
1.7k472135
accept rate: 11%

edited 27 Mar '16, 22:31


Is it really that easy, that it is given tag "Easy" ?

link

answered 15 Mar '16, 15:11

hmishra2250's gravatar image

5★hmishra2250
111
accept rate: 0%

2

I replaced the difficulty rating with "medium" based on accept rate.

(15 Mar '16, 15:42) kevinsogo7★

A very nice editorial to a "tough seeming" problem.

link

answered 24 Mar '16, 01:29

thedark's gravatar image

5★thedark
862
accept rate: 9%

I Did it in a very different ways i applied dfs in conditions and checked if the loops were satisfiable and counted no. of edges which were fixing values of edges i mean every condition fixed value of one edge if it wasn't completing a loop and lastly got the answer (2^left no. of edges)

link

answered 15 Mar '16, 20:52

killjee's gravatar image

6★killjee
2699
accept rate: 6%

Please explain with an example. It is very difficult to understand.

link

answered 15 Mar '16, 21:50

prudvinit's gravatar image

3★prudvinit
10317
accept rate: 0%

I also did the same thing but did not get accepted ? Was your solution accepted ? My answer passed on 10 test cases out of 19 .

link

answered 17 Mar '16, 15:04

mummy's gravatar image

1★mummy
1
accept rate: 0%

I m also not able to understand solution :(

link

answered 17 Mar '16, 21:50

codejavax's gravatar image

5★codejavax
1
accept rate: 0%

"So our strategy now is to instead count the number of assignments of the xi's." What did u mean by counting the number of assignments of xi's??

link

answered 21 Mar '16, 00:59

maan_j's gravatar image

2★maan_j
1
accept rate: 0%

edited 21 Mar '16, 01:07

It means: "How many ways are there to assign values to $x_1$, $x_2$, ..., $x_N$ in a way that satisfies the constraints?"

(26 May '16, 19:11) kevinsogo7★
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:

×11,590
×1,831
×932
×189
×135
×37
×7

question asked: 13 Mar '16, 14:25

question was seen: 3,693 times

last updated: 26 May '16, 19:11