Problem: chain_explosions (2020 round3)

Dynamite is an [effective tool](https://youtu.be/7AheBqBk0iQ?t=433) for clearing ice to allow logs to flow downstream in the great Canadian log drive. But as every Canadian knows, successful use of dynamite requires a certain finesse. Logan the logging director is planning to hook up a network of dynamite sticks using fuse wires so that they may be detonated from afar.

Logan would like to use at most 2000 sticks of dynamite and at most 2000 fuse wires to build his dynamite network at a certain job site. He'll number the sticks from \(1\) to \(N\), and the wires from \(1\) to \(M\) (for some \(N\) and \(M\) of his choice). Each fuse wire is used to connect two different sticks of dynamite together. No two fuse wires may be used to connect the same unordered pair of sticks. The resulting dynamite network must all be connected (that is, it must be possible to reach each dynamite stick from each other stick by following a sequence of connected wires and sticks).

There's just one problem: sticks of dynamite are not individually powerful enough to break the thick ice. Logan must rely on *chain explosions* to amplify the dynamite's power. A potential chain explosion can occur anywhere in Logan's network where there is an ordered triple \((a, b, c)\) of distinct sticks of dynamite such that sticks \(a\) and \(b\) are connected by a fuse wire, as are sticks \(b\) and \(c\). Logan would like to build a network with exactly \(K\) potential chain explosions, where \(K\) is an even integer. Any less than \(K\), and there might not be enough ice-breaking power; any more than \(K\), and he risks damaging the logs.

Help Logan bust some ice by constructing *any* valid dynamite network for the given value of \(K\). Please note that at least one valid network exists for each possible valid value of \(K\).

# Constraints

\(1 \le T \le 100\)
\(2 \le K \le 2,000,000\)
\(K\) is even

The sum of \(K\) across all job sites is at most 10,000,000.

# Input

Input begins with an integer \(T\), the number of job sites. For each job site, there is a line containing a single integer \(K\).

# Output

For the \(i\)th job site, print a line containing *"Case #i: "*, followed by 2 integers \(N\) and \(M\), the number of sticks of dynamite and fuse wires your network will use \((1 \le N, M \le 2000)\). After that, print \(M\) more lines, the \(j\)th of which contains 2 integers \(A_j\) and \(B_j\), the two sticks of dynamite connected by the \(j\)th fuse wire \((1 \le A_j, B_j \le N, A_j \ne B_j)\).



# Explanation of Sample

***Note: For each job site, other outputs would also be accepted.***

For the first job site, the chosen network (depicted below) has exactly 2 potential chain explosions (involving dynamic stick triples \((1, 2, 3)\) and \((3, 2, 1)\)), as required.

{{PHOTO_ID:636021084002078}}

For the second job site, the chosen network (depicted below) has exactly 6 potential chain explosions (involving sticks \((1, 2, 3)\), \((1, 3, 2)\), \((2, 1, 3)\), \((2, 3, 1)\), \((3, 1, 2)\), and \((3, 2, 1)\)).

{{PHOTO_ID:2943967372557617}}

The following output would *not* be accepted, due to having a fuse wire connecting a stick of dynamite to itself (stick 3) and having two fuse wires connecting the same unordered pair of dynamite sticks (sticks 1 and 2):

```
3 5
1 2
2 1
2 3
3 3
3 1
```

The following output would also *not* be accepted, due to the dynamite network not being connected:

```
7 5
1 2
2 3
3 4
5 6
6 7
```

For the third job site, the chosen network is as follows:

{{PHOTO_ID:326196371830360}}


Sample input:
3
2
6
18


Sample output:
Case #1: 3 2
1 2
2 3
Case #2: 3 3
1 2
2 3
3 1
Case #3: 5 6
5 1
3 2
2 4
2 5
4 1
3 5


Solution: 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.


Code: // Chain Explosions
// Solution by Jacob Plachta

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x < 0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x * x); }
string plural(string s) { return(Sz(s) && s[Sz(s) - 1] == 'x' ? s + "en" : s + "s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#define GETCHAR getchar_unlocked

bool Read(int& x)
{
  char c, r = 0, n = 0;
  x = 0;
  for (;;)
  {
    c = GETCHAR();
    if ((c < 0) && (!r))
      return(0);
    if ((c == '-') && (!r))
      n = 1;
    else
      if ((c >= '0') && (c <= '9'))
        x = x * 10 + c - '0', r = 1;
      else
        if (r)
          break;
  }
  if (n)
    x = -x;
  return(1);
}

void ProcessCase()
{
  // input
  int K;
  Read(K), K /= 2;
  // construct graph
  int N = 2;
  vector<PR> E = { { 1, 2 } };
  while (K)
  {
    int r = N, d = 1;
    while (d <= K)
      E.pb({ r, ++N }), K -= d++;
  }
  // output
  printf("%d %d\n", N, Sz(E));
  for (auto e : E)
    printf("%d %d\n", e.x, e.y);
}

int main()
{
  int T, t;
  Read(T);
  Fox1(t, T)
  {
    printf("Case #%d: ", t);
    ProcessCase();
  }
  return(0);
}