Simons and Posting Blogs

Research note: I checked the official Codeforces editorial and the problem page. The official intended solution is the same reverse greedy idea; the supplied statement is the canonical version here.

The operation looks like a deque simulation problem, but the actual invariant is simpler: after all mentions are processed, $Q$ is ordered by decreasing time of last mention. The first element is the user mentioned most recently, the second is the user whose last mention is next most recent, and so on. Earlier mentions of the same user are dead weight.

So for one blog $a_i$, if we view it from the end to the beginning and keep each user only the first time we see it, we get its effective reverse block $b_i$. Example: $[6,1,1]$ becomes $[1,6]$. That is exactly what this blog can contribute to the final $Q$ when we process blogs in reverse posting order.

Now choose the blogs in reverse. Maintain a set $U$ of users already placed into the answer. For every unchosen blog, keep its current block after deleting users from $U$. If we choose blog $i$ now, we append this current block to the answer, add its users to $U$, and delete those users from every remaining block.

The greedy step is: choose the lexicographically smallest current block. Do not sort once and call it a day; after every chosen block, the other blocks shrink. That mutation is the whole problem, because of course the blogs had to be annoying.

Why the greedy is safe:

Let $g$ be the lexicographically smallest current block, and compare it with any other possible first choice $x$.

If $g$ and $x$ first differ at some position and $g$ has the smaller value there, then every answer starting with $g$ is immediately lexicographically smaller than every answer starting with $x$.

The only subtle case is when $g$ is a prefix of $x$. Write $x = g \circ d$. If we take $g$ first, then all values of $g$ are deleted from $x$, so $x$ becomes exactly $d$ because every block has distinct values. Then we can choose this shortened $x$ next and reproduce the same prefix $g \circ d$ that choosing $x$ first would have produced. The optimal continuation after taking $g$ can only be better. Empty blocks are just the same prefix argument with $g=[]$.

Therefore there is always an optimal solution whose next reverse blog is the smallest current block. Repeating by induction gives the globally lexicographically smallest $Q$.

Implementation details:

1. For each blog, read its list, scan it right-to-left, and keep each value once. This gives the initial block.
2. Repeat $n$ times: scan all unfinished blogs and pick the lexicographically smallest current block.
3. Append that block to the answer and mark its users as used.
4. If the block was nonempty, rebuild every unfinished block by removing used users.

Let $L=\sum_i l_i$. Preprocessing is $\mathcal O(L)$. Each round compares all remaining blocks and filters at most the total current length, so the total is $\mathcal O(n^2+nL)$, easily fine for $n,L\le 3000$. Memory is $\mathcal O(L+10^6)$ for the blocks and timestamp arrays.