Git Gud

The important move is to stop thinking about one hidden skill and instead track all possible skills at once.

Initially the possible set is

$$S=\{1,2,\ldots,n\}.$$

If we do a mission with difficulty $y$ and duration $l$, then only the possibility $y$ changes. It becomes $y+l$. So, at the set level:

$$S \leftarrow (S \setminus \{y\}) \cup \{y+l\}$$

if $y \in S$. If $y \notin S$, the mission is useless. Very inspirational stuff.

Our goal is to shrink all possibilities below $n$ into $n$.

Choosing the duration

Suppose we already decided to use difficulty $y$, and $y \in S$.

The cheapest useful thing is to merge $y$ into the next larger possible skill:

$$l = \operatorname{next}_S(y)-y.$$

Then $y+l$ is already in $S$, so the number of possible skills decreases by $1$. Any larger duration is more expensive and does not help more for this construction.

So from now on, the real problem is: in what order do we delete the numbers $1,2,\ldots,n-1$ from this ordered set?

Why the dumb orders fail

If we delete in increasing order:

$$1,2,3,\ldots,n-1,$$

every duration is $1$, which is great, but every next difficulty is larger than the previous one, so we pay the $1000$ tax about $n$ times. Dead on arrival.

If we delete in decreasing order:

$$n-1,n-2,\ldots,1,$$

we almost never pay the $1000$ tax, but the gaps explode. After deleting $n-1$, deleting $n-2$ needs duration $2$, then duration $3$, and so on. Also dead.

So we want chunks that are decreasing, while keeping gaps controlled.

The modulo idea

Pick a base $m$. For the large test, we can use

$$m=63.$$

First, we force every possible skill to become congruent to $n$ modulo $m$.

For example, if $m=3$, we delete residue class $n-2$ first:

$$n-2,\ n-5,\ n-8,\ldots$$

and then residue class $n-1$:

$$n-1,\ n-4,\ n-7,\ldots$$

Each list is decreasing, so there is no surcharge inside it. Also, every deleted value merges into the next larger value, so every duration is $1$.

After this layer, the only remaining possible skills are congruent to $n$ modulo $m$.

Next layers

Now survivors are spaced by $m$. To force them to be congruent to $n$ modulo $m^2$, we do the same thing, but with step size $m$.

More generally, suppose after some layers all remaining values are congruent to $n$ modulo $p$.

To upgrade this to modulo $pm$, delete the bad residue classes. For $r=m-1,m-2,\ldots,1$, output

$$y=n-rp,\ n-rp-mp,\ n-rp-2mp,\ldots$$

while $y\ge 1$.

Every mission in this layer has duration $p$, because the next still-possible value above $y$ is exactly $y+p$. If $r>1$, that target residue will be processed later in the same layer; if $r=1$, it lands in the final residue for this layer.

After the layer, only numbers congruent to $n$ modulo $pm$ survive.

We repeat this while $p<n$. Once $p \ge n$, the only number in $[1,n]$ congruent to $n$ modulo $p$ is $n$ itself. That means every starting skill has been merged into $n$, so the strategy guarantees success.

Cost

For $n=250000$ and $m=63$:

$$63^3 = 250047 \ge 250000,$$

so we need exactly $3$ layers: $p=1,63,3969$.

In one layer with spacing $p$, we output at most $n/p$ missions, each of duration $p$, so the duration cost of a layer is at most $n$. Across $3$ layers, that is at most

$$3n = 750000.$$

The surcharge happens only when jumping from the end of one decreasing residue-class block to the start of the next one. There are at most $3\cdot 62$ nonempty blocks, so the surcharge is below

$$3\cdot 62\cdot 1000 = 186000.$$

Total cost is below $936000$, safely under $10^6$.

The number of missions is exactly $n-1$ for the large test, because every value below $n$ is deleted once. That is also below $10^6$.

For $n=4$, we can just print the tiny sample construction. The problem literally has only two tests, so no need to cosplay as a general-purpose library.