P5419 [CTSC2016] Monotonically Increasing Sequence

For a weighted undirected graph, we can study its monotonically increasing paths. A path is called monotonically increasing if, when you traverse it, the edge weights are monotonically increasing. Note that a path consists of multiple edges connected end to end, and it may pass through the same vertex multiple times. The length of a path is the number of edges it contains. For example, in the figure below, $v_2 \rightarrow v_4 \rightarrow v_1 \rightarrow v_2$ is a monotonically increasing path, because the weights of its edges are $1,2,4$. The length of this path is $3$. Furthermore, you can verify that in the figure below, the length of every monotonically increasing path is at most $3$.  The following statement shows that in some graphs, there will always be a relatively long monotonically increasing path: Statement: Suppose a weighted undirected graph $G$ has $100$ vertices and $1000$ edges, and all edge weights are pairwise distinct. Then there must exist a monotonically increasing path in $G$ whose length is at least $20$. Proof: Suppose there is an explorer on each vertex. We enumerate all edges in increasing order of weight, and each time we swap the positions of the explorers on the two endpoints of the current edge. It can be seen that each explorer walks along a monotonically increasing path. Also, since there are $100$ explorers and the explorers walk a total of $2000$ steps, someone must have walked $20$ steps. QED. Now, our problem is: You are given a complete graph $G$ whose number of vertices is an even number $N$. Your task is to assign a distinct weight to each edge so that the length of the longest monotonically increasing path is as small as possible.

The input contains only one line with a positive even integer $N$.

Output a permutation of the integers $1$ to $\frac{N(N-1)}{2}$, with adjacent numbers separated by a single space or a newline. The first number represents the weight you assign to edge $(1,2)$; the second number is the weight for $(1,3)$; $\ldots$; the $N$-th number is the weight for $(1,N)$. Then come the weights for $(2,3)$, $(2,4)$, $\ldots$, $(2,N)$. Then the weights for $(3,4)$ to $(3,N)$, and so on. Finally, output the weight for $(N-1,N)$.

#### Constraints and Notes - For $20\%$ of the testdata, $N \leq 20$. - For $50\%$ of the testdata, $N \leq 100$. - For $100\%$ of the testdata, $2 \leq N \leq 500$. #### Notes Besides different subtasks having different characteristics, you may also receive partial credit on each test. If your program can terminate correctly and output in the required format, we will score it as follows: Suppose the length of the longest monotonically increasing path in your graph is $A$, and the correct answer is $B$. - If $A=B$, your score is $10$ points. - If $B < A < 2B$, your score is $3$ points. - If $A \geq 2B$, your score is $0$ points. Translated by ChatGPT 5