Share your ideas for solving XDCOMP .

sshhhh · February 13, 2019, 6:32pm

Everyone in the community , can you share and discuss/debate over your ideas for solving XOR Decomposition appearing in Feb Long Div 1 ?

aryanc403 · February 13, 2019, 6:43pm

I don’t know why this works.
And why this fails.
I stress tested to find those if-else
My idea was to reduce this problem to the vertex with values. 0,X
And then I made all cases up to 3 vertices on paper. And then It was stress test.

shoom · February 13, 2019, 8:37pm

Here is high level steps:

First, I converted a tree into a possibly smaller tree by combining nodes that not equal to x or zero into their parents (using XOR) until the merged node is either zero or x.
The result is a tree with all nodes equal to x or zero.
Second, you can recursively calculate the number of ways to split the tree from number of ways to split each sub-tree. Separately keep track of number of ways to split a subtree that cause the subtree root node to be part of a group of even number of x’s (XOR’ing to zero) and part of a group of odd number of X’s.
Let’s consider a simple example of a sub-tree of three X nodes (one parent and two child nodes). It can be split in three ways as shown in the diagram below. The first and fourth ways cause the parent node to be in a group that XOR’s to x and the second and third ways have the parent node to be in a group that XOR’s to zero. The resulting count for this subtree can be represented as {0: 2, x: 2} or [2, 2] in short.
```
  X    |    X     |    X    |    X
 / \   |   /      |     \   |
X   X  |  X    X  |  X   X  |  X   X
```
Here is another example, with 3 children nodes, one of which is zero. Note, that zero child should always be connected to a parent, since only groups XOR’ed to x are allowed in the final split. Thus the result is still {0:2, x:2}.
```
  X    |    X    |    X    |    X
 /|\   |   /|    |    |\   |    |
X 0 X  |  X 0 X  |  X 0 X  |  X 0 X
```
You can work out a formula how to combine pairs of numbers {0: n1, x: n2} from sub-trees into a pair of number for a parent tree.
Each zero node needs to be combined either with its parent or with one of its children.
Separately need to take care of the case when X = 0. In this case the answer is the total number of ways to split that derived tree from step 1, which is 2^(N-1), where N is the number of nodes in a merged tree.

aman_robotics · February 13, 2019, 8:49pm

I solved it in the same way, except I assigned a value 0 and 1 to the nodes, in the new merged tree . Value 0 were assigned to the nodes with xor_sum 0 and value 1 was assigned to the nodes with xor_sum equal to x.
Now the problem just reduced to calculate the number of ways to split the edges such that each independent tree in the forest(of new tree) has odd sum of values.
My soln : https://www.codechef.com/viewsolution/23030105

bad_jim · February 13, 2019, 8:58pm

Do a depth first search. For each node, you want to return:

The number of ways to split off an odd number of subtrees that xor to x.
The number of ways to split off an even number of subtrees that xor to x.
The xor sum of the subtree.

When you get back to root:

if the xor sum of the whole tree is x, you return the number of ways to have an even number of splits(which means an odd number of subtrees).
If the xor sum is 0, you return the number of ways to have an odd number of splits.
If x = 0 and the xor sum is 0, you return the sum of these.
Otherwise, you return 0 because it is impossible.

A leaf node has 0 splits, which is an even number.

If a subtree has a xorsum of x, it can be split there, so there is an extra way to have an odd number of splits for every way to have an even number of splits.

If a subtree has a xorsum of 0, it can also be split, and there is an extra way to have an even number of splits for every way to have an odd number of splits.

You may need to be careful about the case where x = 0 when doing this.

My code

shoom · February 13, 2019, 8:59pm

Yes, I also replaced X’s with 1’s in the merged tree for convenience.
https://www.codechef.com/viewsolution/22935893

striver_79 · February 13, 2019, 9:43pm

@aman_robotics my too was the same to reduce the problem to odd sum of values.

vipin1407 · February 13, 2019, 9:59pm

This Question is very much similar to this codeforce problem. Here is an excellent editorial for the codeforce question. You can implement XDCOMP similar to this.

b123eginner · February 23, 2019, 9:37pm

Hi @vipin1407 , can you explain your solution. I am unable to understand why are you doing theif(k){ } in dfs(). Is this to count the number subtrees rooted at v that have a xor value ‘X’ when v is not included in u’s subtree ?
And how does this program handles the case when this is not possible.