South American Qualifiers

Store only the points that the remaining teams still have to earn from matches among themselves.

Suppose $m$ teams remain. Let

$$(a_1,a_2,\cdots,a_m)$$

be their required remaining scores, kept in sorted order. Team names do not affect the rest of the feasibility problem, so sorting gives a canonical state.

Removing one team

Choose one team and decide all of its matches against the other $m-1$ teams. If the chosen team wins, it receives 3 points and the opponent receives 0. A draw gives 1 point to each team. If the chosen team loses, it receives 0 points and the opponent receives 3.

If the chosen team's target is $x$, consider only assignments in which these $m-1$ matches give it exactly $x$ points. For every opponent, subtract the points earned in this match from that opponent's remaining target. Then remove the chosen team. The remaining $m-1$ teams form exactly the same kind of complete round-robin problem.

This gives the following recursion.

• With no teams left, the state is feasible.
• With one team left, the state is feasible exactly when its remaining target is 0.
• Choose one team and enumerate all possible outcomes of its matches against the other teams.
• Update the opponents' remaining targets, remove the chosen team, and recurse.

Correctness

Assume that a feasible set of match results exists. For any chosen team, take the actual outcomes of its $m-1$ matches. This assignment is among the cases enumerated by the recursion. After subtracting the opponents' points from those matches and removing the chosen team, the actual results of all remaining matches form a feasible solution to the smaller state. Therefore the recursion never misses a feasible tournament.

Conversely, suppose the recursion chooses an assignment for the selected team's matches and the recursive call succeeds. Combining those selected-team matches with the recursively constructed matches determines every match among the current $m$ teams exactly once, and every team receives exactly its required points. Therefore every successful recursive branch corresponds to a valid tournament.

Canonical states and memoization

Team labels are irrelevant, so sort every state before memoizing it. Opponents with the same remaining target are interchangeable. Group equal targets together and enumerate only how many teams in each group are beaten, drawn with, and lost to. This avoids exploring permutations of the same assignment.

As a branching heuristic, remove a team with the smallest number of possible $(W,D,L)$ triples first, where $W+D+L=m-1$ and $3W+D=x$.

Necessary-condition pruning

The following conditions are checked before branching.

• A target $x$ for a team with $g=m-1$ matches remaining must admit nonnegative integers $W,D,L$ satisfying $W+D+L=g$ and $3W+D=x$.
• There are $\binom{m}{2}$ remaining matches, so the total remaining score must lie between $2\binom{m}{2}$ and $3\binom{m}{2}$.
• For the smallest $k$ targets in sorted order, their sum is at least the points produced by matches among those $k$ teams themselves, namely $2\binom{k}{2}=k(k-1)$.
• The largest $k$ teams can obtain points only from matches incident to those teams. Their total therefore cannot exceed $3\left(\binom{k}{2}+k(m-k)\right).$

All of these are necessary conditions, so any state violating one of them can be rejected immediately.

The number of teams is the fixed constant 10. With global memoization of canonical residual-score states, different test cases also reuse many subproblems, which comfortably handles $T\leq 200$.

Solution written by GPT5.6