SRM 691, D1, 300-Pointer (Sunnygraphs)

James S. Plank

Sun Nov 13 00:50:37 EST 2016

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.

Obviously, this was a difficult problem. The solution that I outline here does indeed work, but I feel as though it's too complex. Maybe someday I'll see a cleaner solution.

General Structure of the Graphs -- Useless nodes

Although the problem tells you to consider the problem as an undirected graph problem, it is much more useful if you view the problem as a directed graph problem. When you do that, and you write out some examples, you should see rather quickly that all of the connected components have a similar structure -- they are composed of one cycle with some paths going into the cycle. Let's give an example, which I'll put in main.cpp as Example 5:

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 multiply 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.

I also annotated each node with a value InCycle, which says whether the node is in a cycle reachable from either node 0 or 1. I did that as part of my DFS's above.

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> a.out 5
Node  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>

Let's look at some other examples. Here are examples 0-3:

UNIX> a.out 0
Node  0:  Useful: 3  InCycle: 1
Node  1:  Useful: 3  InCycle: 1
#Useful:  0  0  0  2
0
UNIX>

UNIX> a.out 1
Node  0:  Useful: 3  InCycle: 1
Node  1:  Useful: 2  InCycle: 0
Node  2:  Useful: 3  InCycle: 1
#Useful:  0  0  1  2
0
UNIX>

UNIX> a.out 2
Node  0:  Useful: 1  InCycle: 1
Node  1:  Useful: 2  InCycle: 1
Node  2:  Useful: 1  InCycle: 1
Node  3:  Useful: 2  InCycle: 1
#Useful:  0  2  2  0
0
UNIX>

UNIX> a.out 3
Node  0:  Useful: 1  InCycle: 0
Node  1:  Useful: 2  InCycle: 0
Node  2:  Useful: 3  InCycle: 0
Node  3:  Useful: 3  InCycle: 1
Node  4:  Useful: 3  InCycle: 1
#Useful:  0  1  1  3
0
UNIX>

Case 1: Nodes 0 and 1 are in different components.

A very simple case to handle is when nodes 0 and 1 are in different components. In order for them to be connected, you will have to change one edge reachable from node 0 to point to the extra node, and one node reachable from node 1 to point to the extra node. In that way, you can get from node 0 to the extra node, and then from the extra node to node 1 (remember, for connectivity, you treat the graph as undirected). You can use example 2 to illustrate this case, but I'm going to add a beefier example as example 6:

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, (2^Y-1) ways to change at least one edge reachable from node 1. So the final answer is:

(2^U)(2^X-1)(2^Y-1).

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 long long's.

UNIX> a.out 2 | tail -n 2
#Useful:  0  2  2  0
9
UNIX> a.out 6
Node  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>

Case 2: Nodes 0 and 1 are in the cycle.

In the remaining cases, nodes 0 and 1 are in the same component. The easiest case here is when they are both in the cycle. In this case, you can do whatever you want to any edge. You will always have a path from 0 to 1. You can recognize this case with Useful -- this case happens when every node either has a usefulness of 0 or 3. Let C be the number of nodes with a usefulness of 3. These nodes will all be on the cycle. The answer will be:

(2^U)(2^C).

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>

Case 3: Node 0 is in the cycle, and Node 1 is not. And Vice Versa

Example 1 falls into this category, but I think you can see the answer more easily if you see a bigger example, like example 7:

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 (2^P-1)(2^C-1). That makes the total:

(2^U)((2^C)+(2^P-1)(2^C-1)).

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

UNIX> a.out 7
Node  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>

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:

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

Case 4: Node 0's path to the cycle goes through node 1. And Vice Versa

Here's Example 11, which fits this case. Let's assign two variables: P is the length of the path from 0 to 1, and R is the number of other, non-useless edges. In the picture below, P is three and R is eight.

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).

So, the total for this one is:

(2^U)((2^R)+(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 11
Node  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 12
Node  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>

Case 5: Node 0 and node 1 have distinct paths to a shared part of the graph

This is the final case, which you can see in Example 3 above, and in examples 9 and 10 below:

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.

And again, we can break up the counting of sets into three cases:

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)).

That gives us the following equation:

(2^U)((2^S)+(2^Y-1)(2^S-1)+(2^X-1)(2^Y+S-1)).

UNIX> a.out 3 | tail -n 2
#Useful:  0  1  1  3
30
UNIX> a.out 9
Node  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 10
Node  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>

An Afterword

I'm sure you can coalesce some cases above, and perhaps frame the problem differently from the way I framed it. However, all you need is the data that I described (Useful, InCycle, and the counts of Useful). I found this problem pretty satisfying to complete.