- Problem Statement.
- A
**main()**with the examples compiled in. - A skeleton that compiles with
**main.cpp**. -
**Problem Given in Topcoder**: May, 2016 -
**Competitors who opened the problem**: 414 -
**Competitors who submitted a solution**: 144 -
**Number of correct solutions**: 91 -
**Accuracy (percentage correct vs those who opened)**: 22.0% -
**Average Correct Time**: 37 minutes, 54 seconds.

You'll note that I've put the nodes into two colors. The yellow nodes are those that are reachable from node 0 or node 1. The green nodes are those that are not reachable from node 0 or node 1. The first observation that I want you to make is that the green nodes have no bearing on whether 0 connects to 1. To help illustrate that, below, I show what happens if you add the extra node to the graph and connect nodes 4, 6, 7 and 8 to it. As you can see, it has no bearing on whether 0 connects to 1:

I'm calling nodes that are not reachable from node 0 or 1 "Useless." Suppose
that there are *U* of them. These nodes have
no bearing on whether 0 connects to 1, so their edges can be set to anything without
affecting the outcome of the problem. So, what we're
going to do is ignore them, and then after we've solved the problem without them, we'll
multiple the return value by *2 ^{U}*. This accounts for all possible setting
of those edges.

So, in Example five, we're going to solve the subproblem of the cycle (0,2,1,5,0), and then multiply the answer by 32.

Time to write some code. In this code, I annotated each node with a value **Useful**.
I started with **Useful** equal to zero for all nodes. Then I set **Useful** equal to
one for all nodes reachable from node 0. And then for all nodes reachable from node 1, I
added two to **Useful**. Because of the limited structure of the graphs, I didn't
need recursion to do this, but I did do a DFS. Think about that.

This means, for every node, I can see the following:

- If
**Useful**equals 0, then the node is useless. - If
**Useful**equals 1, then the node is only reachable from node 0. - If
**Useful**equals 2, then the node is only reachable from node 1. - If
**Useful**equals 3, then the node is reachable from both 0 and 1.

Finally, for each value from 0 to 3, I count the number of nodes that have that value
for **Useful**.

Let's look at some outputs. Here's the output on Example 5 (the figure above). As you can see, the four cycle nodes are reachable from 0 and 1, and the rest are useless:

UNIX>Let's look at some other examples. Here are examples 0-3:a.out 5Node 0: Useful: 3 InCycle: 1 Node 1: Useful: 3 InCycle: 1 Node 2: Useful: 3 InCycle: 1 Node 3: Useful: 0 InCycle: 0 Node 4: Useful: 0 InCycle: 0 Node 5: Useful: 3 InCycle: 1 Node 6: Useful: 0 InCycle: 0 Node 7: Useful: 0 InCycle: 0 Node 8: Useful: 0 InCycle: 0 #Useful: 5 0 0 4 0 UNIX>

UNIX> |
UNIX> |

UNIX> |
UNIX> |

You'll note that there are two useless nodes here, so we'll solve the problem without them, and then multiply the final answer by 4. To make nodes 0 and 1 connect, we need to change any edge from any node reachable from 0, and to change any edge from any node reachable from 1. Can we change more than one edge? Sure. We just have to change at least one. The picture below shows us changing one edge reachable from node 0 (the edge from 2), and two edges reachable from node 1 (edges from 6 and 7). As you can see, nodes 0 and 1 are now connected, when we treat the graph as undirected:

How do we count the cases? Well, let's call the number of nodes reachable from 0: *X*.
And, let's call the number of nodes reachable from 1: *Y*.
Then, there are *(2 ^{X}-1)* ways to change at least one edge reachable
from node zero,
and,

You'll note that you can calculate these from the **Useful** counts. In example 2, the
answer is 1*3*3 = 9, and in example 6, the answer is 4*7*15 = 420.

Write up this code. Use bit shifting to calculate *2 ^{anything}*, and remember to use

UNIX>a.out 2 | tail -n 2#Useful: 0 2 2 0 9 UNIX>a.out 6Node 0: Useful: 1 InCycle: 0 Node 1: Useful: 2 InCycle: 0 Node 2: Useful: 1 InCycle: 1 Node 3: Useful: 0 InCycle: 0 Node 4: Useful: 1 InCycle: 1 Node 5: Useful: 2 InCycle: 1 Node 6: Useful: 2 InCycle: 0 Node 7: Useful: 2 InCycle: 1 Node 8: Useful: 0 InCycle: 0 #Useful: 2 3 4 0 420 UNIX>

We can test this with example 0, whose answer will be 4. Example 5 also fits this category. Its answer should be 32 * 16 = 512:

UNIX>a.out 0 | tail -n 2#Useful: 0 0 0 2 4 UNIX>a.out 5 | tail -n 2#Useful: 5 0 0 4 512 UNIX>

You can break this into two cases. In the first case, you don't change any edges on the path from 1 to the cycle. In that case, you can do whatever you want with the edges in the cycle -- you'll always be able to connect nodes 0 and 1.

On the flip side, suppose you do change an edge on the path from 1 to the cycle. Then, node 1 is disconnected from the cycle. In order to connect it, you have to change at least one edge on the cycle.

Let's call the cycle length *C* and the path length to the cycle *P*.
Case one is *(2 ^{C})*, and case two is

In the example above (example 7), that is 2*(16+(7*15)) = 242. In example 1, it is 1*(4+1*3) = 7.

UNIX>Obviously, you can solve the case where node 1 is in the cycle, and node 0 isn't, very similarly. Example 8 is like example 7, but with nodes 0 and 1 switched:a.out 7Node 0: Useful: 3 InCycle: 1 Node 1: Useful: 2 InCycle: 0 Node 2: Useful: 3 InCycle: 1 Node 3: Useful: 0 InCycle: 0 Node 4: Useful: 2 InCycle: 0 Node 5: Useful: 3 InCycle: 1 Node 6: Useful: 3 InCycle: 1 Node 7: Useful: 2 InCycle: 0 #Useful: 1 0 3 4 242 UNIX>a.out 1 | tail -n 2#Useful: 0 0 1 2 7 UNIX>

UNIX>a.out 8 | tail -n 2#Useful: 1 3 0 4 242 UNIX>

We can break this one into two cases:

- Case A: No edges on the path from 0 to 1 are changed. In that case,
you can do whatever you want with the remaining edges:
*2*.^{R} - Case B: At least one edge on the path from 0 to 1 is changed. In that
case, you'll have to change at least one of the remaining edges:
*(2*.^{P}-1)(2^{R}-1)

We test in on example 11, pictured above, and example 12, which is the same as example 11, except I've switched nodes 0 and 1.

UNIX>a.out 11Node 0: Useful: 1 InCycle: 0 Node 1: Useful: 3 InCycle: 0 Node 2: Useful: 3 InCycle: 0 Node 3: Useful: 3 InCycle: 0 Node 4: Useful: 3 InCycle: 0 Node 5: Useful: 3 InCycle: 1 Node 6: Useful: 3 InCycle: 1 Node 7: Useful: 1 InCycle: 0 Node 8: Useful: 3 InCycle: 1 Node 9: Useful: 3 InCycle: 1 Node 10: Useful: 0 InCycle: 0 Node 11: Useful: 1 InCycle: 0 #Useful: 1 3 0 8 4082 UNIX>a.out 12Node 0: Useful: 3 InCycle: 0 Node 1: Useful: 2 InCycle: 0 Node 2: Useful: 3 InCycle: 0 Node 3: Useful: 3 InCycle: 0 Node 4: Useful: 3 InCycle: 0 Node 5: Useful: 3 InCycle: 1 Node 6: Useful: 3 InCycle: 1 Node 7: Useful: 2 InCycle: 0 Node 8: Useful: 3 InCycle: 1 Node 9: Useful: 3 InCycle: 1 Node 10: Useful: 0 InCycle: 0 Node 11: Useful: 2 InCycle: 0 #Useful: 1 0 3 8 4082 UNIX>

Example 9: |

Example 10: |

Now, nodes 0 and 1 both have paths, composed of edges that they don't share with the other, to a segment of shared edges. This latter segment includes the cycle. Again, let's label the sizes of these paths/segments:

- The number of edges uniquely reachable from node 0 is
*X*. - The number of edges uniquely reachable from node 1 is
*Y*. - The number of edges in the shared segment is
*S*.

- Case A: We don't change any edges uniquely reachable from nodes 0 or 1.
In that case, we are either connected
directly (as in Examples 3 and 10), or we are connected to the cycle (as in Example 9).
We can change any of the edges in the shared segment:
*2*.^{S} - Case B: We don't change any edges uniquely reachable from 0,
but we do change at least on from 1.
In that case, we have to change at least one edge in the shared segment:
*(2*.^{Y}-1)(2^{S}-1)) - Case C: We change at least one edge uniquely reachable from 0. In that case, we have
to change at least one of the edges from node 1 -- that would be either an edge
uniquely reachable from node 1, or an edge in the shared segment:
*(2*.^{X}-1)(2^{Y+S}-1))

UNIX>a.out 3 | tail -n 2#Useful: 0 1 1 3 30 UNIX>a.out 9Node 0: Useful: 1 InCycle: 0 Node 1: Useful: 2 InCycle: 0 Node 2: Useful: 2 InCycle: 0 Node 3: Useful: 2 InCycle: 0 Node 4: Useful: 2 InCycle: 0 Node 5: Useful: 3 InCycle: 1 Node 6: Useful: 3 InCycle: 1 Node 7: Useful: 1 InCycle: 0 Node 8: Useful: 3 InCycle: 1 Node 9: Useful: 3 InCycle: 1 Node 10: Useful: 0 InCycle: 0 #Useful: 1 2 4 4 2012 UNIX>a.out 10Node 0: Useful: 1 InCycle: 0 Node 1: Useful: 2 InCycle: 0 Node 2: Useful: 2 InCycle: 0 Node 3: Useful: 2 InCycle: 0 Node 4: Useful: 3 InCycle: 0 Node 5: Useful: 3 InCycle: 1 Node 6: Useful: 3 InCycle: 1 Node 7: Useful: 1 InCycle: 0 Node 8: Useful: 3 InCycle: 1 Node 9: Useful: 3 InCycle: 1 Node 10: Useful: 0 InCycle: 0 #Useful: 1 2 3 5 2028 UNIX>