Longest Increasing Path (Hard Version)

The statement is basically output-only with two fixed inputs. That matters. We do not need a beautiful theorem for every possible $(n,m)$; we need one deterministic construction that gives at least $299999$ increasing jumps using at most $15000$ values.

The clean way to think about this is graph-theoretic.

Pick some integer points. Treat each point as a vertex. An edge between two vertices has weight equal to the distance between the two corresponding integers. We need a walk whose edge weights strictly increase.

So we will build a sparse graph on at most $15000$ points, where the edge weights are real distances from the chosen coordinates. Then we find a longest increasing path in that sparse graph. If the graph contains a long enough increasing path, the vertex coordinates along that path are exactly the required sequence.

The block gadget

Take two blocks of equal size $K$:

$$p_1<p_2<\cdots<p_K, \qquad q_1<q_2<\cdots<q_K.$$

Assume every $p_i$ is to the left of every $q_j$. Then this sequence is magic:

$$p_K,q_1,p_{K-1},q_2,p_{K-2},q_3,\ldots,p_1,q_K.$$

The jump lengths are

$$q_1-p_K, q_1-p_{K-1}, q_2-p_{K-1}, q_2-p_{K-2}, \ldots, q_K-p_1.$$

Each next edge moves one endpoint outward, so the distance increases. If both blocks are consecutive integers, it increases by exactly $1$ each time. No sorcery, just endpoints walking away from each other.

This gives $2K-1$ jumps for one pair of blocks.

Many blocks

Use

$$B=46,\qquad K=301.$$

That is $46\cdot301=13846$ ordinary block points.

For block $i$, define its center as

$$c_i=2^{i+13}-2^{13}\quad(0\le i<46),$$

and put the $301$ values

$$c_i-150,c_i-149,\ldots,c_i+150.$$

The powers of two are doing one job: they separate block distances. The tiny $[-150,150]$ offsets are irrelevant compared to the gap between consecutive centers.

For every pair of blocks $(lo,hi)$ with $lo<hi$, add all edges from the zigzag gadget between those two blocks.

If we only did that, we would have tons of good local paths but stitching them by hand would be painful. Painful is bad. We add transition edges.

Transition points

Inside a pair $(lo,hi)$, the zigzag naturally can end at the high endpoint of block $hi$. To begin another zigzag involving the same upper block, it is useful to be at the low endpoint of block $hi$.

A direct jump inside the block is tiny, so it would break increasingness. Instead, for each needed transition we create one extra point $T$ to the right of block $hi$.

Let

$$H=c_{hi}+150, \qquad L=c_{hi}-150.$$

For the transition after pair $(lo,hi)$, place

$$T=H+\bigl(H-(c_{lo}-150)\bigr)+1.$$

Then

$$|T-H|=\text{previous pair max}+1,$$

and

$$|T-L|=\text{previous pair max}+301.$$

Both are safely larger than the previous pair's internal jumps, and still safely smaller than the next lower-block pair because powers of two leave a stupid amount of slack.

There are

$$\sum_{hi=2}^{45}(hi-1)=990$$

such transition points. Total distinct values used:

$$13846+990=14836\le15000.$$

The largest coordinate is below $6\cdot10^{17}$, so the $10^{18}$ bound is fine.

Let DP do the stitching

Now we have a sparse weighted undirected graph:

• vertices are the constructed integer values;
• edges are block-pair zigzag edges plus transition edges;
• edge weight is the actual absolute distance.

We need a longest path with strictly increasing edge weights. This is the standard DP over sorted edges:

Let $dp[v]$ be the maximum number of edges in an increasing path ending at vertex $v$ after processing all smaller edge weights.

For an edge $(u,v)$ of current weight $w$, we may extend:

$$dp[u]\leftarrow dp[v]+1, \qquad dp[v]\leftarrow dp[u]+1.$$

Edges of equal weight must be processed as one batch, because the path needs strictly increasing distances. So we first collect all updates for the same weight, then apply them.

We also store persistent parent nodes. That is important: if we just stored parent[v], later updates to $v$ could overwrite the old path and corrupt reconstruction. Classic little bug, very annoying, easy to dodge.

For these constants, the DP finds a path with over $623000$ jumps. We only need $299999$, so we reconstruct the best path and take a suffix of length $n$ vertices.

Finally, the code verifies the output before printing. If the sequence has length $n$, uses at most $m$ distinct values, stays in bounds, and every jump is larger than the previous one, then it is valid. That's the whole checker condition, no hidden crap.