SRM 730, D1, 500-Pointer (Subgraphs)

James S. Plank

Sat Sep 1 00:43:30 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: February, 2018
Competitors who opened the problem: 171
Competitors who submitted a solution: 63
Number of correct solutions: 51
Accuracy (percentage correct vs those who opened): 29.8%
Accuracy (percentage correct vs those who submitted): 80.9%
Average Correct Time: 33 minutes, 9 seconds.

This one is more about figuring out the problem than the programming, although my solution was a straightforward dynamic program.

I'm not going to include any drawings here, sorry. If you are giving this problem in CS494/594, you should draw a bunch of graphs to help give some intuition about the problem and its solution.

So, when I started on this problem, I took pencil to paper and drew a bunch of graphs. I came to the following realizations:

My solution for k should have 2k nodes. I'm guessing 2k-1 will work, but I'm going to concentrate on 2k.
If I have a solution for k-1 nodes, I'll add two nodes to its graph to get to the solution for k nodes. I won't connect the first of these. That way, the solutions for k-1 will also be the solutions for k, by simply adding this new node to the set.
I hate to blast math at you so soon, but whatever. If you have a solution for k-1, that solution will have sets for every number of edges up to and including (k-1)(k-2)/2. That means the previous bullet gets you every number of edges up to and including (k-1)(k-2)/2. Since you need to find sets for every number of edges up to and including k(k-1)/2, that means you need to find sets for (k-1)(k-2)/2+1 to k(k-1)/2 edges. That means you have to find k-1 sets (subtract (k-1)(k-2)/2 from k(k-1)/2).
Those k-1 sets must include the second of the two nodes that you have added.

Given those realizations, it came upon me that if I connect the second of the two nodes to every one of the nodes in the graph for k-1, then I have solved the problem! If I need to find a set that has exactly e edges, and e > (k-1)(k-2)/2, then I use the set from the solution for k-1 that has e-(k-1) edges, and add the second of the two nodes to the set. You'll note that the solution for k-1 has k-1 nodes. By adding the second node to the set, my set has k nodes, which is what we want, and I've just added k-1 edges to the graph, giving me a total of e edges. How cool is that!

So, the solution works as follows. Let G(k) be the graph for k. And let S(n,k) be the set of nodes in G(k) that has exactly n edges. Your goal is, given a value of k to define G(k) and then to find S(n,k) for every value of n from 0 to k(k-1)/2.

We start with a base case, where k = 1. In that case, k(k-1)/2 equals 0, so you only care about finding G(1) and S(0,1). The solution to this is simple -- G(1) is a single node with no edges, and S(0,1) is that node.

Now we attack the general problem.

We assume that we have solved the problem for k-1. Then, G(k) equals G(k-1) plus two new nodes, which I'll call l_k and h_k. There are no edges coming out of l_k. On the flip side, h_k has an edge to every other node in the graph except l_k.

That's the graph. Let's turn our attention to S(n,k). Suppose that n ≤ (k-1)*(k-2)/2. Then S(n,k) = S(n,k-1) ∪ { l_k }. Otherwise, S(n,k) = S(n-(k-1),k-1) ∪ { h_k }. Man, that's awesome.

When I programmed this, I rendered the previous paragraph as a dynamic program, and memoized. It passed the topcoder system tests easily.

OK, if you're reading this because you need to present this in CS594, you had better be drawing a lot of pictures. You should draw G(k) for k ≤ 4, and show how you get S(n,k) from S(n,k-1) or from S(n-(k-1),k-1) pictorally. It's a challenging problem to present, but with good graphics, this will be a really fun problem to present!

And while I'm at it, when you're trying to figure out the running time of the program, ask yourself how the number of characters in the return value scales with k. Are you doing O(1) work for each character in the return value?