Defender of Childhood Dreams
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 2500
Tags: bitmasks, constructive algorithms, divide and conquer

Even if you just leave them be, they will fall to pieces all by themselves. So, someone has to protect them, right?

You find yourself playing with Teucer again in the city of Liyue. As you take the eccentric little kid around, you notice something interesting about the structure of the city.

Liyue can be represented as a directed graph containing $$$n$$$ nodes. Nodes are labeled from $$$1$$$ to $$$n$$$. There is a directed edge from node $$$a$$$ to node $$$b$$$ if and only if $$$a < b$$$.

A path between nodes $$$a$$$ and $$$b$$$ is defined as a sequence of edges such that you can start at $$$a$$$, travel along all of these edges in the corresponding direction, and end at $$$b$$$. The length of a path is defined by the number of edges. A rainbow path of length $$$x$$$ is defined as a path in the graph such that there exists at least 2 distinct colors among the set of $$$x$$$ edges.

Teucer's favorite number is $$$k$$$. You are curious about the following scenario: If you were to label each edge with a color, what is the minimum number of colors needed to ensure that all paths of length $$$k$$$ or longer are rainbow paths?

Teucer wants to surprise his older brother with a map of Liyue. He also wants to know a valid coloring of edges that uses the minimum number of colors. Please help him with this task!

Input format:
The only line of input contains two integers $$$n$$$ and $$$k$$$ ($$$2 \leq k < n \leq 1000$$$).

Output format:
On the first line, output $$$c$$$, the minimum colors you need to satisfy the above requirements.

On the second line, print a valid edge coloring as an array of $$$\frac{n(n-1)}{2}$$$ integers ranging from $$$1$$$ to $$$c$$$. Exactly $$$c$$$ distinct colors should exist in the construction. Print the edges in increasing order by the start node first, then by the second node.

For example, if $$$n=4$$$, the edge colors will correspond to this order of edges: ($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$), ($$$3$$$, $$$4$$$)

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The corresponding construction for the first test case looks like this:

The corresponding construction for the second test case looks like this:

Example input:
5 3

Example output:
2
1 2 2 2 2 2 2 1 1 1

Example input:
5 2

Example output:
3
3 2 2 1 2 2 1 3 1 1

Editorial:
The minimum number of colors that you need is $$$\lceil \log_k n \rceil$$$.
To achieve this, you can divide the nodes into $$$k$$$ contiguous subsegments of equal size (or as close as possible). Any edge between nodes in different subsegments, you color with $$$1$$$ for example. Then you recursively solve those subsegments excluding the color that you used.
Any path of the same color is between same size subsegments inside a single bigger subsegment (or the whole array). Since there would be only $$$k$$$ such subsegments, the path could only have length at most $$$k - 1$$$.
The highest recursion depth is $$$\lceil \log_k n \rceil$$$, so this is the number of colors used as desired.
We will now prove that $$$\lceil \log_k n \rceil$$$ colors are necessary. We will do this by equivalently proving that if you have a valid coloring using $$$c$$$ colors, then $$$n$$$ is at most $$$k^c$$$. This, in turn, we will prove by induction on $$$c$$$.
The base case is $$$c = 0$$$. If you have no colors, then you can't color any edges, so $$$n$$$ must be at most $$$1 = k^0$$$.
For the inductive step, we assume that any valid coloring using at most $$$c - 1$$$ colors can have at most $$$k^{c - 1}$$$ nodes, and we desire to show that any valid coloring using at most $$$c$$$ colors can have at most $$$k^c$$$ nodes. To do this, we will choose an arbitrary color, then partition all our nodes into at most $$$k$$$ groups such that inside each group, there are no edges of that color. It follows that each group is colored using at most $$$c - 1$$$ colors and so can have at most $$$k^{c - 1}$$$ nodes, so overall we can have at most $$$k \cdot k^{c - 1} = k^c$$$ nodes.
The partition is defined as follows: we will partition the nodes into the sets $$$s_0, s_1, \ldots, s_{k - 1}$$$ where $$$s_j$$$ contains all nodes $$$a$$$ such that the length of the longest path ending in $$$a$$$ using only edges of our chosen color is exactly $$$j$$$. This length is at most $$$k - 1$$$ since our coloring can't have paths of length $$$k$$$ of a single color. Furthermore, there can't be edges of our chosen color inside a set $$$s_j$$$, because otherwise the endpoint of such an edge would be the end of the longest path to the start point of the edge plus the edge itself, which would be of length $$$j + 1$$$.
Therefore, any valid coloring using $$$c$$$ colors can have at most $$$c^k$$$ nodes, and so we must use at least $$$\lceil \log_k n \rceil$$$ colors in our construction, which we have already seen how to do.