Hints: Ghostfires

You must build a longest string using at most $r,g,b$ copies of R,G,B with no equal letters at adjacent positions and none at distance three (i.e.\ $s_i \ne s_{i+1}$ and $s_i \ne s_{i+3}$—“two ghostfires in between”).

Before constructing, what simple upper bound on the length can you get by sorting the three counts?

Answer to Hint 1: Let $x \ge y \ge z$ be the multiset of $(r,g,b)$ sorted. You cannot use more than all balls: length $\le r+g+b$. A tighter structural bound is $\le 2(y+z)+1$: two smaller colors act as separators for the largest one in a near-alternating pattern. Take $\min(r+g+b,, 2(y+z)+1)$ as bestLen (see upper_bound_len in the model).

Answer to Hint 2: If only one color has positive count, the answer is a single character of that color.

If exactly two colors appear, why is a repeated ABAB… (possibly with one extra A) always the right shape?

Answer to Hint 3: You must alternate to satisfy $s_i \ne s_{i+1}$. Distance-$3$ constraints still allow period-$2$ patterns. Let counts be $a \ge b$ for colors A and B. You can place $\min(a,b)$ disjoint AB pairs; you may append one extra A if $a > b$. The model uses useB = min(a,b) and useA = min(a, b+1).

Answer to Hint 4: From here on assume all three colors exist. Compare bestLen to $r+g+b$. If `bestLen < r+g+b$, one color is dominant (too many to interleave with the other two in a full ternary pattern).

What repeating skeleton uses the dominant color between every other color’s letter?

Answer to Hint 5: Sort $(r,g,b)$ with characters; let mx be the largest count and others the multiset of the other two colors. Emit mx, then one letter from others, repeatedly, until others is exhausted; if mx still has surplus, append one more mx. This yields length $2\cdot|\text{others}|$ or $2\cdot|\text{others}|+1$ and matches the dominant regime (solve_dominant_case).

Answer to Hint 6: If bestLen == r+g+b (balanced regime), no shortcut dominates; you need a backtracking search that respects both adjacency and distance-$3$ bans.

What local information must the DFS remember so that adding the next letter never creates $s_i=s_{i+3}$?

Answer to Hint 7: Remember the last up to three placed letters (s0,s1,s2 in the model): a new color cannot equal the previous letter, nor the letter three steps back.

Why is memoizing (remaining counts, last three letters) not enough—you also need a feasibility check before committing?

Answer to Hint 8: Even if the next letter is locally legal, you might make the remaining multiset impossible to finish. After tentatively decreasing a count, compute upper_bound_len on the remaining triple; if it is strictly less than the number of balls left, prune that branch.

Answer to Hint 9: When several colors are still feasible, try a deterministic tie-break (e.g.\ larger remaining count first, then smaller color id) so the search converges quickly; on failure, mark the (counts, suffix) state as dead and backtrack like the model’s unordered_set<State> dead.

Answer to Hint 10: On backtrack, restore counts, pop the last character, insert the current partial state into dead, and try the next candidate at the same position; if no candidate works, recurse further back.

If the DFS returns shorter than bestLen, should you ever extend the string?

Answer to Hint 11: The theoretical maximum for this multiset is bestLen; if you ever produce length bestLen, stop. If implementation length exceeds bestLen due to bugs, truncate to bestLen (as in the model’s safety resize).

Answer to Hint 12: Complexity is kept manageable because each step has at most three choices and heavy pruning removes infeasible branches early—sum of $r+g+b$ across tests is bounded ($10^6$).

Answer to Hint 13: Per test: branch on {1,2,3} colors; single-color and two-color paths short-circuit; three-color balanced uses DFS; print any valid string of maximum length.