Hints : H. Counting Sort?

The map $f$ sends a length-$n$ array $b$ to $f(b)$, where $f(b)_i$ counts how many entries of $b$ are equal to $i$ (only $i \in \{1,\ldots,n\}$ are defined). If you ignore the order of positions and only remember how many times each value appears, does that change $f(b)$?

Answer to Hint 1: No. Each $f(b)_i$ is a count over positions, so $f(b)$ depends only on the multiset of entries of $b$, not their order.

The harder part is understanding $g(b)$. You repeatedly set $d \gets f(d)$ and collect every $d$ in a set $S$. After a huge number of steps, why is it wrong to think you literally need $10^{100}$ iterations?

Answer to Hint 2: There are only finitely many length-$n$ arrays with entries in $\{0,\ldots,n\}$. The map $d \mapsto f(d)$ has out-degree $1$ everywhere, so the sequence must eventually repeat. Once a value appears again, no new arrays ever appear afterward. So $g(b)$ is just the number of distinct arrays on the walk from the start until the first repetition (equivalently: the functional-graph “rho” picture: a tail plus one simple cycle).

Answer to Hint 3: Try the first example sizes. For $[0,1]$ versus $[1,0]$: compute $f$ once. For $[1,0]$: is it a fixed point? For $[0,1]$: how many distinct arrays appear before things repeat?

Separately: values equal to $0$ in $b$ do not increase any $f(b)_i$ for $i \ge 1$. Why can $0$s still change the dynamics?

Answer to Hint 4: Zeros occupy slots and change which multiset of positive symbols you have. They never show up directly in $(f(b)_1,\ldots,f(b)_n)$, but they matter because they steal positions from nonzero values.

Now fix a concrete array $b$ and suppose you want $g(b)$ without solving the full counting problem. What is the simplest reliable algorithm on a computer when $n \le 50$?

Answer to Hint 5: Simulate: keep the current array, apply $f$ in $O(n)$ time using a frequency table of size about $n$, push every visited array into a hash set keyed by the full vector (or by a multiset hash), and stop when you revisit a state. Then $g(b)$ is the number of distinct vectors you saw.

This is already a good “subtask”: given $b$, compute $g(b)$. The orbit is not astronomically long in practice for these maps, so hashing the full length-$n$ vector is usually enough for learning and small tests.

Answer to Hint 6 (optional compression). Since $f(b)$ depends only on the multiset of entries of $b$, you may hash a sorted multiset representation instead of remembering an order across indices.

The reference solution compresses further: it walks values from $n$ down to $1$ and maintains a non-increasing string whose characters encode a multiset of positive integers related to how many indices take each value. Another operation nxt transforms that string. What does nxt do at the English level?

Answer to Hint 7: Group consecutive equal characters in the sorted string (these are “runs”). Record each run’s length. Sort those lengths in non-increasing order and write them as a new string of digits (same convention as the model code).

That step is exactly “take multiplicities of equal parts, then sort those multiplicities”—the heart of iterating $f$ on histogram-shaped data.

Answer to Hint 8: If you compare iterating nxt on that canonical string with repeatedly applying $f$ on arrays, you should see the same high-level orbit, up to the special bookkeeping the program does for empty and "1" tail cases.

For the counting problem (original constraints), why might you iterate $x = n,n-1,\ldots,1$ when deciding an array $a$ satisfying $0 \le a_i \le r_i$?

Answer to Hint 9: On generic branches, repeated nxt on the compressed multiset tracks the same shape information as iterating $f$ on the histogram sequence; the program only layers extra fixes for degenerate tails (empty string and the lone-symbol case).

For the counting problem, think of assigning values from large to small. When you fix how many indices will equal $x$, you only affect indices $i$ that can still reach $x$, namely those with $r_i \ge x$. Indices already forced above $x$ are already decided.

Let $R_x$ be the number of indices with $r_i \ge x$. If you already placed some total “mass” consistent with larger values, how many indices are still free at level $x$?

Answer to Hint 10: Informally, among the $R_x$ indices that could still take values at least $x$, only some remain unfilled after handling $x{+}1,\ldots,n$. Call the slack free. Choosing exactly how many of those positions equal $x$ is achoose-style choice; the model multiplies by a binomial coefficient $\binom{\mathrm{free}}{\mathrm{cnt}}$ when it adds $\mathrm{cnt}$ copies at $x$.

Finally, why does the program’s get function on the string state relate to labeling an answer index $p$ where $g(a)=p$, at least away from the hand-checked corner cases?

Answer to Hint 11: Along a generic branch, the recursion get measures a depth of repeated nxt until a tiny base pattern, and the aggregation uses one more than that depth to map a terminal DP state to a value of $g(a)$. Empty and single-1 strings are special because of all-zero arrays and tiny fixed-point behavior; the solve routine adjusts those contributions explicitly.

Read the longer walkthrough on the editorial page if you want the full subtask ladder and a line-by-line map to model_sol.cpp.