### PROBLEM LINK:

**Author:** Roman Furko

**Tester:** Hiroto Sekido, Gerald Agapov

**Editorialist:** Ajay K. Verma

### DIFFICULTY:

Easy-Medium

### PREREQUISITES:

Connected components

### PROBLEM:

We are given an array of N elements and a set of M intervals. Initially all the elements in the array are set to zero. In a single operation an interval is picked and all the array elements inside that interval are flipped. The task is to find out how many different arrays can be obtained by applying the above operation repeatedly.

### QUICK EXPLANATION:

Refer to the next section.

### EXPLANATION:

Let us start with an example. Suppose we have 5 intervals: [3, 5), [2, 4), [2, 8), [4, 8), and [2, 13). Note that all the intervals are represented in left-closed, right-open way (i.e., the left end point is included in the interval, while right end point is not).

We perform operations on the array based on the above intervals, and obtain sequences. Let us say we have one such sequence w. The sequence w will start with a series of 0’s, at some point it will make a transition to a series of 1’s and then back to 0’s and so on. The positions at which these transitions happen must be one of the end points of the given intervals. We call these positions as the critical position of the sequence. It is easy to see that if we know the critical position of a sequence, and its length, we can in fact construct the sequence. In other words, there is a one-to-one correspondence between the subset of critical positions and the sequences obtained. Hence, the task reduces to find the number of valid subsets of critical positions.

Any subset of critical positions will only contain the positions which are the end points of some of the given M intervals. For example if, we flip the interval [2, 4), [4, 8) and [3, 5), then the obtained sequence will be [0, 1, 0, 0, 1, 1, 1, 0, …], which has critical positions {2, 3, 5, 8}.

It can be seen easily that if we pick a set of intervals I_{1}, I_{2}, …, I_{k} and flip then, then an endpoint will be a critical position in the obtained sequence if and only if this endpoint occurs in an odd number of the chosen intervals. In the above example 4 is the endpoint of two intervals [2, 4) and [4, 8), hence it is not among the critical positions of the sequence, while all other endpoints are the endpoints of a single intervals, and hence they are among the critical positions of the sequence.

This is because whenever we pick an interval it is equivalent to insert two critical positions corresponding to the endpoints of the interval, it means that we need to make a transition at these positions. However, if any of these positions are already present in the set of critical positions, then we are basically trying to make a double transition at this position, which is equivalent to no transition at all.

### Reduction into a graph problem:

Based on the above observation, we can create a graph where nodes correspond to the end points of the given M intervals. For each interval, we create an edge between the nodes corresponding to its endpoints. Each edge can be labeled as 0 or 1, representing whether the corresponding interval is picked or not. For a given labeling of the edges, we can compute the critical positions of the obtained sequence easily: For each node compute the XOR of labels of edges incident on this node, if the value is one, then this endpoint is one of the critical positions of the sequence, otherwise it is not.

So now the problem reduces to the following: We are given an undirected graph, and we are allowed to label each edge as 0 or 1. How many different set of node labels can be obtained by such labeling (the label of a node is the XOR of the labels of edges incident on it).

The advantage of this reduction is that we can partition the graph into connected components, compute the number of possible node labels for each component, and then multiply these values together to get the number of possible node labels of the whole graph.

### Number of node labels in a connected component:

In this section we show that if a connected graph has n nodes, then the number of possible node labels is (2^{n-1}). The proof is easy and is based on induction. First, we show the result for a tree, and then show that adding an edge between the nodes already connected does not affect the result.

#### Tree:

If there is a single node, then only one node label is possible namely zero. If there are two nodes connected by edge, then two node labels are possible: (0, 0) if the edge label is 0, and (1, 1), when the edge label is 1.

Now assume that the result holds for any tree with n nodes. And we insert a new node by connecting it to one of the existing node v. If we label the inserted edge as 0, then the new node will have label zero, while all other nodes will have the same label as before, i.e., we have 2^{n-1} labels. On the other hand, if we label the inserted edge as 1, then the new node will have label 1, the label of v is flipped, and all other nodes will their label unchanged, i.e., we have additional 2^{n-1} labels. This means, for a tree of (n + 1) nodes we have 2^{n} possible node labels, which completes the induction step.

#### Edge insertion between two nodes which are already connected:

Let us say we have nodes u and v which are already connected by a path consisting of edges e_{1}, e_{2}, …, e_{k}. Now, if we connect the two nodes by an edge e, the labeling of this edge as 1 is equivalent to flip the label of node u and v, while keeping the labels of all other nodes as is. This could have also been achieved by flipping the edge labels of e_{1}, e_{2}, …, e_{k}. In other words, inserting the edge (u, v) does not create any extra set of node labels.

This completes the proof that number of node labels of a connected graph with n nodes is 2^{n-1}.

### Algorithm:

Create the graph corresponding to intervals as described above. Let us say this graph has m nodes. Compute the connected components of the graph. Let us say there are k connected components of size m_{1}, m_{2}, …, m_{k}, then the answer would be

2^{m1-1} * 2^{m2-1} * … * 2^{mk-1}

= 2^{m-k}

### TIME COMPLEXITY:

O (M)

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution will be put up soon.

Tester’s solution will be put up soon.