Noogler_from_Google's blog

Number of simple path with xor value of k
By Noogler_from_Google, history, 3 years ago, In English

Yesterday I encountered this problem in a hiring contest.

Problem:

You are given the following:

  1. A tree T consisting of n nodes

  2. An integer x

  3. Each node has some value w[i] associated with it.

Task

Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x.

Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once.

Example

Assumptions

n = 3 w = [3,2,2] edges = [(1,2), (1,3)] x = 1 Approach

There exist two simple paths such that bitwise xor of elements on the path is x Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator. Therefore, print 2.

Any approach?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

what is the number of nodes ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This can be done using dsu on tree.

First compute prefix-xor for each node from root. For each sub-tree rooted at u, compute number of nodes with v such that prefix_xor[parent[u]]^prefix_xor[v]==k or prefix_xor[v] = k^prefix_xor[parent[u]] // number of paths from node u to v with xor equals to k

For each pair of nodes (v1,v2) such that v1 and v2 are siblings computed prefix_xor[v1]^prefix_xor[v2]^node_val[u] = k or prefix_xor[v1] = k^node_val[u]^prefix_xor[v2] // number of paths which passes through node u and xor on a path equals k

overall complexity would be : $$$\mathcal{O}(n\log{}n)$$$

→ Reply
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Centroid Decomposition can also be used to solve this.

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Since the nodes are only 1000, this can be done in O(n*n), just run a dfs from each node, and count the number of pairs for which the x is valid. Another way can be using binary lifting for each pair of vertices (with an extra log(n) factor on the compexity)

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    dumb question but for the first approach if the pair(x,y) is included for root of dfs as x then pair(y,x) will also be included for root of dfs as y. so we include it just once right? like if (x,y) is valid then don't increment the count for (y,x)?

    and for the second approach its based on the fact that (xor_till_x_from_1) ^ (xor_till_y_from_1) ^ (value_at_lca_of_x&y) ?

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Let node 1 be the root. s[i] means the value from root to i.

Caculate how many (x, y) satisfy s[x] ^ s[y] ^ a[lca(x, y)] = k

when Lca is fixed, you need to caculate s[x] ^ s[y] = k ^ a[lca(x, y)], with x and y is in different subtree of Lca.

Dsu on tree, remove (x, y) in the same subtree

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can solve this problem with Small To Large Merging technique.

→ Reply