Longest Increasing Path (Easy Version)

The easy version has only two inputs, and the big one is fixed:

$n=100000,\quad m=15000.$

So we are not trying to solve a general optimization problem. We just need one reliable construction that prints enough terms while using at most $15000$ different values.

The dumb approach is dead instantly: if we keep moving to fresh coordinates, we need about $100000$ distinct values. We only get $15000$. So the walk must reuse values while the jump lengths keep increasing.

The Two-Block Gadget

Take two blocks of consecutive values, each of odd size $S$:

$P_0,P_1,\ldots,P_{S-1}$

and

$Q_0,Q_1,\ldots,Q_{S-1},$

with the whole $Q$ block far to the right of the whole $P$ block.

Visit them like this:

$P_{S-1},Q_0,P_{S-2},Q_1,P_{S-3},Q_2,\ldots,P_0,Q_{S-1}.$

Every jump goes between the two blocks. If the center distance is $D$, then the jump lengths are

$D-(S-1),\ D-(S-2),\ \ldots,\ D+(S-1).$

So this one gadget gives

$2S-1$

strictly increasing jumps using only values from two blocks. Nice little machine.

Many Gadgets

Now create $K=50$ blocks, each of size $S=201$. Their centers are

$C_i=2^{i+10}-2^{10}.$

Inside block $i$, use the consecutive values centered at $C_i$.

For a pair of blocks $(a,b)$ with $a<b$, every jump inside its gadget lies in

$[C_b-C_a-(S-1),\ C_b-C_a+(S-1)].$

Because the centers grow like powers of two, these intervals are cleanly separated if we process pairs in this order:

• increasing right block $b$;
• for each $b$, decreasing left block $a$;
• only the last few $a$ near $b$.

That gives a lot of block-pair gadgets, and their internal jump lengths are globally increasing.

Transitions

The only annoying part is moving from the end of one gadget to the start of the next.

Suppose the previous jump length is $L$, and the first jump inside the next gadget is $R$. A transition jump is legal if its length is strictly between them:

$L < t < R.$

Let

$\ell=L+1,\quad h=R-1.$

We need to move by some signed displacement $T$ using jumps whose absolute lengths are strictly increasing and lie in $[\ell,h]$.

There are several simple cases:

• If $T$ itself lies in $[\ell,h]$, use one jump.
• If $T$ is small, use two jumps: first go the wrong way by $\ell$, then the right way by $\ell+T$.
• If $T$ is medium, use three jumps of the form

$-x+y+z=T,$

with

$x<y<z.$

• If $T$ is large, move in one direction using $k$ increasing lengths whose sum is $T$.

For the last case, the smallest possible sum with $k$ jumps is

$k\ell+\frac{k(k-1)}2,$

and the largest possible sum is

$kh-\frac{k(k-1)}2.$

So once $T$ lies in that interval, start with

$\ell,\ell+1,\ldots,\ell+k-1$

and distribute the remaining amount from right to left.

This is enough for the fixed large test. The construction reaches $100000$ terms while staying under $15000$ distinct printed values. The largest coordinate is below $2^{59}$, so the $10^{18}$ bound is also fine.

The small test is just printed directly. Since hacks are disabled and the statement literally tells us the only inputs, this is not being cute; it is using the damn input format.