hackercupai/hackercup huggingface dataset:
We need to construct an undirected, connected graph with exactly \(K\) length-2 simple paths. The bounds indicate that we may only use up to roughly \(\sqrt{K}\) nodes and edges in this graph.

If we let \(D_i\) be the degree of node \(i\), we can observe that there are \(D_i (D_i - 1)\) length-2 simple paths for which node \(i\) is the middle node. There are multiple ways to use this observation to construct a valid graph, with one simple method described below.

We'll begin with a graph having 2 nodes (numbered \(1\) and \(2\)) connected by an edge. Note that this graph contains no length-2 simple paths. We'll then repeat the following process until it has \(K\) length-2 simple paths.

Let \(r\) be the largest-numbered node currently present in the graph. We'll be constructing the graph such that the degree of the largest-numbered node at any point is always known to equal \(1\) (note that this is the case in the initial graph). We'll now repeatedly add new nodes to the graph (numbered \(r+1\), \(r+2\), and so on), connecting each one to node \(r\) by an edge, until adding another such node would cause the graph to have more than \(K\) length-2 simple paths. Each time such a node is added, \(2 D_r\) length-2 simple paths are added to the graph, and then \(D_r\) increases by \(1\). Note that each new node's degree is \(1\), and the last of the added nodes will become node \(r\) for the next iteration of the process (if any).

The above approach uses fewer than 1,500 nodes and edges for any even \(K\) up to 2,000,000, comfortably under the limit of 2,000.