RRAHSEM - Editorial

PROBLEM LINK:

Practice
Contest

Problem statement:

Initially we have an empty graph and we have N(N<=2e5) queries. In each query we are given a number X(X<=1e18), which means we have to add a new node to a graph whose value is X. This node has edges to all other nodes such that bitwise XOR of value of these two nodes is a power of 2. That is the values differ in exactly one bit. Find the number of connected components after each query.

Observation:

  1. The number of different values that a node can connect is 60 as X<=1e18.
  2. If a node with value X and value Y belong to the same component then any occurrence of X and Y that comes in the query from hereon doesn’t affect the number of connected components.

Solution:

Prerequisites : DSU (Disjoint Set Union Data structure)

If X and Y differ by exactly one bit then we need to merge nodes with value X to nodes with value Y.
So if there are 1e5 occurrences of X and 1e5 occurrences of Y then we need to 1e10 merges which is intractable. So for each distinct value if we have a representative node then we connect the representative nodes alone and our answer doesn’t change due to observation-2.

The merges that is discussed in the previous paragraph is done by DSU data structure efficiently. Since our value can lie anywhere between 1 to 1e18, we need to compress them to use DSU.

  1. DSU merge works in log$*$N
  2. Co-ordinate compression takes logN
  3. Number of connection values is log(1e18)

Time Complexity : O(N$logNlog(1e18)log$N)

C++ Solution

//