Encode and Decode (Hard Version)

The whole trick is realizing this is not really an “interactive brain-melter.” It is just serialization with a weird alphabet and a length limit. The jury runs our program twice, memory gets wiped, and the only thing surviving is the lowercase string $s$. So we need a reversible way to pack the array into lowercase letters.

Capacity check

Each lowercase letter can represent one digit from $0$ to $25$:

• a means $0$
• b means $1$
• ...
• z means $25$

That means a block of $k$ letters can store $26^k$ different values.

We need to store numbers up to $10^9$. Check powers:

$26^6 = 308915776$

Not enough. But:

$26^7 = 8031810176$

That is more than enough. So every value $a_i$ fits in exactly $7$ lowercase letters if we write it in base $26$.

Also $n \le 10^4$, so $n$ obviously fits in $7$ letters too.

Encoding plan

Encode the data as fixed-size blocks:

$[n][a_1][a_2]\cdots[a_n]$

where each block is exactly $7$ characters long.

For a number $x$, repeatedly take:

$d = x \bmod 26$

append character a + d, then divide:

$x = \left\lfloor \frac{x}{26} \right\rfloor$

Do this exactly $7$ times. This stores the number in little-endian base $26$, meaning the lowest digit comes first. Little-endian is fine because decoding will use the same convention. No need to be precious about it.

Decoding plan

Read the string in chunks of length $7$.

To decode one block, reconstruct:

$x = d_0 + 26d_1 + 26^2d_2 + \cdots + 26^6d_6$

where $d_i = s[pos+i] - \texttt{'a'}$.

The first decoded block gives $n$. Then decode the next $n$ blocks to recover the array.

Length proof

There are $n+1$ blocks: one for $n$, and one for each array element.

Each block has length $7$, so:

$|s| = 7(n+1)$

Since $n \le 10^4$:

$|s| \le 7 \cdot 10001 = 70007$

The limit is $10^5$, so we are comfortably under it. Not even close. The constraint tried to look scary and then folded.

Correctness proof

For every encoded number $x$, the algorithm writes exactly its first $7$ base-$26$ digits. Since every relevant number satisfies $x < 26^7$, those $7$ digits represent $x$ uniquely.

During decoding, we read the same $7$ digits and compute the base-$26$ value from them. Therefore each decoded block equals the original encoded number.

The first block is $n$, so decoding recovers the original length. The following $n$ blocks are exactly $a_1, a_2, \ldots, a_n$, so the full original array is recovered.

Therefore the algorithm always outputs the correct original data in the second run.

Complexity

Encoding takes $O(n)$ time and outputs $7(n+1)$ characters.

Decoding also takes $O(n)$ time.

Memory usage is $O(n)$ only for storing the array/string, easily within limits.