Minimizing the Longest Increasing Path in a Complete Graph

Given a complete undirected graph \(G\) with an even number of vertices \(N\), you are to assign a unique weight to every edge (i.e. all weights are distinct) such that the length (number of edges) of the longest strictly increasing path is minimized.

A strictly increasing path is defined as a sequence of edges \(e_1, e_2, \ldots, e_k\) (where each two consecutive edges share a common vertex and vertices may be repeated) satisfying

[ w(e_1) < w(e_2) < \cdots < w(e_k), ]

where \(w(e)\) denotes the weight on edge \(e\). The length of a path is the number of edges it contains.

Your task is to choose a weight assignment (using the integers \(1, 2, \ldots, \tfrac{N(N-1)}{2}\)) for all edges in \(G\) so that the longest increasing path in \(G\) is as short as possible.

Note: The graph is complete, meaning every pair of distinct vertices is connected by an edge. It is guaranteed that \(N\) is even.

Example:

For instance, consider the complete graph with \(N = 4\). If vertices \(1, 2\) form the first half and vertices \(3, 4\) form the second half, one possible assignment is as follows:

• Assign the lowest weights to cross edges between the two halves: edges \((1,3)\), \((1,4)\), \((2,3)\), \((2,4)\) get weights \(1,2,3,4\) respectively.
• Then assign the remaining higher weights to the edges within each half: edge \((1,2)\) gets weight \(5\) and edge \((3,4)\) gets weight \(6\).

The output is an \(N \times N\) matrix \(M\) where \(M[i][j]\) (for \(i j\), \(M[i][j] = M[j][i]\); and \(M[i][i] = 0\) for all \(i\).

inputFormat

The input consists of a single line with an even integer \(N\) (\(2 \le N \le 200\)), the number of vertices in the complete graph \(G\).

outputFormat

Output an \(N \times N\) matrix. The \(j\)-th number in the \(i\)-th row denotes the weight of the edge between vertices \(i\) and \(j\). For \(i = j\), output 0. The weight assignment should use each integer from \(1\) to \(\tfrac{N(N-1)}{2}\) exactly once and follow your strategy to minimize the longest strictly increasing path.

sample

2

0 1
1 0