Compare Suffixes

Research sources used: the official Codeforces statement (https://codeforces.com/problemset/problem/2206/A) and the official ICPC APAC problem analysis PDF (https://apac26.icpc.tw/assets/championship/2026/problemset-analysis.pdf).

The budget is the whole problem. If we treat suffixes like random comparable objects, comparison sorting needs about $n\log_2 n$ queries, roughly 10000 for $n=1000$. The limit is 6260, so that plan is toast. The missing structure is that these objects are suffixes of the same string.

Process suffixes from right to left. Suppose we already know the suffix array of $S(x+1),S(x+2),...,S(n)$, stored as

$S(p_0)<S(p_1)<...<S(p_{k-1})$.

Also keep inverse ranks $rank[i]$, and define a fake empty suffix $S(n+1)$ with $rank[n+1]=0$. This sentinel makes suffix $S(n)$ behave cleanly: if two suffixes start with the same character and one shifted suffix is empty, the same comparison rule still works.

Now look at adjacent known suffixes $S(a)<S(b)$. If their first characters are equal, then removing that first character preserves the comparison:

$S(a)<S(b)$ iff $S(a+1)<S(b+1)$.

So if $rank[a+1]>rank[b+1]$, equal first characters are impossible. That adjacent place must be a boundary between different starting letters. Call it a splitting position.

Because the suffix array is lexicographically sorted, suffixes starting with a come before suffixes starting with b, and so on. Therefore there are at most 25 boundaries between first-letter groups, hence at most 25 splitting positions. This is the whole trick: the string alphabet smuggles in a tiny constant.

Split the current suffix array at all positions where

$rank[p_i+1]>rank[p_{i+1}+1]$.

Inside each resulting segment, the shifted ranks $rank[p_i+1]$ are strictly increasing.

Now insert $S(x)$. Its tail $S(x+1)$ is already ranked, so let $t=rank[x+1]$. In one segment, if inserting $S(x)$ does not create a new split, then its predecessor inside that segment is forced: it must be the last suffix $S(p_i)$ in the segment with

$rank[p_i+1]<t$.

Since shifted ranks are increasing inside the segment, this candidate is found by binary search without asking the judge. Do this once per segment. There are at most 26 segments, plus a sentinel candidate before everything.

These candidate predecessor positions are sorted in the actual suffix-array order. Binary-search them with real interactive queries of the form: is $S(p_i)<S(x)$? This costs at most $ceil(log_2 27)=5$ queries. Let $c$ be the largest candidate known to be smaller than $S(x)$.

Then verify with one more query:

• If $c$ is the last current position, insert at the end.
• Otherwise ask whether $S(x)<S(p_{c+1})$.
• If yes, the exact insertion position is $c+1$.
• If no, our candidate list missed the true predecessor, meaning this insertion created a new splitting position. Then we just do normal binary search over the whole current suffix array.

Why can the expensive fallback happen only 25 times? Every fallback is charged to a newly appearing splitting position. A split certifies a boundary between different first-letter groups, and a lowercase alphabet has only 26 groups, so at most 25 such boundaries can be charged. This is the part where the problem looks scary but the alphabet quietly does all the heavy lifting.

Query count:

• Every insertion costs at most 6 queries in the normal case.
• At most 25 insertions pay an extra full binary search, at most $ceil(log_2 1000)=10$ queries.

So for $n=1000$:

$6(n-1)+25*10 <= 6244 <= 6260$.

The local computation is simple: rebuilding ranks and inserting into a vector gives $O(n^2)$ time, which is tiny for $n<=1000$. Memory is $O(n)$.

Interactive details: print each query, flush immediately, read first/second, and after printing answer ..., terminate. No extra chatter; the judge is not your therapist.