Incremental Subarray

The array $b$ is not random at all. It is just blocks glued together:

$$[1], [1,2], [1,2,3], \ldots, [1,2,\ldots,n]$$

So every adjacent pair in $b$ has one of two forms:

• inside a block: $x \to x+1$;
• between blocks: $k \to 1$, where $k$ is the length of the block that just ended.

That is the whole problem. The rest is just not lying to ourselves.

Case 1: no boundary inside $a$

Suppose every adjacent pair satisfies

$$a_{i+1}=a_i+1.$$

Then $a$ is just a consecutive increasing chunk like $[3,4,5]$. It cannot cross a block boundary, because crossing a boundary would create a transition to $1$.

So it must sit inside a single block. If the last value is $a_m$, then any block of length at least $a_m$ contains this exact chunk once, starting at value $a_1$.

The valid block lengths are:

$$a_m, a_m+1, \ldots, n$$

so the count is

$$n-a_m+1.$$

For example, with $n=5$ and $a=[1,2,3]$, it appears in blocks $3,4,5$, so the answer is $3$.

Case 2: at least one boundary inside $a$

A boundary in $a$ is a place where

$$a_i \to a_{i+1}=1.$$

Then this must be the end of a block. Since the value at the end of block $k$ is exactly $k$, this boundary forces that block to be block $a_i$.

That is extremely restrictive. Once you know one boundary, the occurrence is pinned to one location in $b$. There cannot be many possible copies floating around. This is an 800-rated problem, not witchcraft.

But we still need to validate multiple boundaries.

If one boundary is after value $k$, then the next block is block $k+1$. Therefore, the next boundary, if it exists, must be after value $k+1$.

So if the boundary-ending values are:

$$L_1, L_2, \ldots, L_s$$

we need:

$$L_{j+1}=L_j+1.$$

Also, after the last boundary after $L_s$, the pattern continues inside block $L_s+1$, so the last value of the pattern must not exceed $L_s+1$, and this block must exist:

$$L_s+1 \le n.$$

If all checks pass, the answer is exactly $1$.

Invalid patterns

Even though the statement guarantees the answer is at least $1$, the implementation can cheaply handle invalid input too. Any adjacent pair that is neither:

$$x \to x+1$$

nor

$$x \to 1$$

is impossible, so the answer would be $0$.

Algorithm

Scan the pattern once.

• If $a_{i+1}=a_i+1$, keep going.
• Else if $a_{i+1}=1$, record a boundary ending at $a_i$.
• Else the pattern is impossible.

After the scan:

• If there were no boundaries, answer $n-a_m+1$.
• Otherwise, check boundary values are consecutive and the final block exists. If yes, answer $1$.

Complexity per test case is $O(m)$, with $m \le 200$. Tiny. Basically free.