Computing competitions

2025 Southeast Regional Solutions

On this page

The problem statements are linked from Kattis. The explanations below preserve the full solution notes and code for the selected UWF problems.

Problem A — Snakey String

Open the original problem on Kattis .

Here is a simple explanation and a clean Python 3 solution.

Solution

Explanation

You are given an r × c grid.
Each column contains exactly ONE uppercase letter (the others are dots).
To recover the original string, you just:
1. Look at each column from left to right.
2. Find the uppercase letter in that column.
3. Append it to the result.

That’s it—no actual snake traversal is needed because the puzzle guarantees exactly one letter per column.

Python 3 Solution

def solve():
    r, c = map(int, input().split())
    grid = [input().strip() for _ in range(r)]

    result = []

    # For each column, find the one uppercase letter
    for col in range(c):
        for row in range(r):
            ch = grid[row][col]
            if 'A' <= ch <= 'Z':  # meaningful letter
                result.append(ch)
                break

    print("".join(result))

if __name__ == "__main__":
    solve()

Problem B — Blind Bottles

Open the original problem on Kattis .

1. The Game in One Minute

There are n bottles, each labeled 1..n, arranged in a secret order.
A guess is a line of n numbers (a rearrangement of 1..n).
After each guess, you’re told how many positions are exactly right.
You win when all positions are right.

Our goal: figure out the secret order using at most 10,000 guesses for n ≤ 100.

2. Big Idea (No heavy math)

We stick to one baseline guess all the way through: the simple list:

1 2 3 ... n

Call its score B (how many spots were already right in that baseline).

Now we learn about the secret order by making very small, controlled changes to this baseline:

Swap just two positions `i` and `j` in the baseline and ask again.

If the score goes up, then those two positions are directly related in the secret ordering (they are neighbors in a loop).
If the score stays the same or goes down, those positions aren’t directly related.

Doing this for every pair `(i, j)` lets us draw a picture (a graph) of who is connected to whom. That picture always breaks into loops:

A single dot (no connections) means that position was already correct.
A pair of dots connected to each other is a simple 2‑swap.
Any longer loop (3 or more) means the correct bottles rotate around that circle of positions.

After we have these loops, we make at most one extra test per long loop to find which way it rotates. Then we can write down the final, correct order and win.

3. Why swapping two spots tells us anything

Think about what the final arrangement looks like around any one position:

There’s the spot where this position’s bottle really belongs.
There’s also the spot whose bottle belongs here.

Those are the two “neighbors” around that position in the final solution. Swapping i and j helps only when i and j are such neighbors (either the bottle from i belongs in j, or the bottle from j belongs in i). That’s exactly why the score goes up when we swap a “neighbor pair”.

4. Step‑by‑step plan

Baseline. Ask the identity order 1 2 … n once. Save the score as B.
Build connections. For every pair of positions (i, j):
- Swap only those two in the baseline and ask again.
- If the score is higher than `B`, draw an edge between i and j.
Read the loops.
- No edges → position already correct (leave it as is).
- One edge → a 2‑swap; those two positions want each other’s bottles.
- Two edges → part of a longer loop (a circle of 3 or more positions).
Decide the direction (for each long loop).
- Try pushing everyone in the loop one step forward (a “rotate once” guess), leaving all other positions as in the baseline.
- If the score jumps by the loop’s length, that is the right direction. Otherwise, it’s the reverse direction.
Write the final answer. Now we know, for each position, which position’s bottle belongs here. Build the full line and print it once.

5. Tiny example (n = 5)

Say the secret order is: [3, 5, 2, 1, 4]

After checking all pair swaps, we discover a single loop:

positions: 1 → 3 → 2 → 5 → 4 → back to 1
That means the correct bottles cycle around those positions.
We do one “rotate once” test on just that loop. If the score jumps by 5, we already have the exact solution; otherwise we reverse the loop.
Either way, we now know the final arrangement and can print it.

6. How many questions do we ask?

One for the baseline.
One for each pair of positions (there are about n(n−1)/2 such pairs; for n = 100 that’s 4950).
At most one extra per longer loop (in the worst case, around 33 of them).
One final print of the full answer.
Total ≤ 4,985 guesses for n = 100, well under the 10,000 limit.

7. The Python solution (Accepted by Kattis)

# Blind Bottles — Python interactive solution
# Deterministic O(n^2) queries (<= 4985 for n<=100)
# Algorithm: pairwise swaps vs identity to reveal cycle adjacencies,
# then 1 query per long cycle to fix its orientation.

import sys

def ask(perm):
    """Print a permutation, flush, and read judge's reply (number of fixed points)."""
    print(" ".join(map(str, perm)), flush=True)
    line = sys.stdin.readline()
    if not line:
        sys.exit(0)  # judge closed
    k = int(line.strip())
    if k == len(perm):
        sys.exit(0)  # solved; judge ends the game
    return k

def main():
    data = sys.stdin.readline()
    if not data:
        return
    n = int(data.strip())

    # 1) Base query: identity
    base = list(range(1, n + 1))
    B = ask(base)
    if B == n:
        return  # already solved

    # 2) For every pair (i, j), swap on top of identity and see if score improves.
    #    If it does, i and j are adjacent in the hidden permutation's cycle.
    adj = [[] for _ in range(n)]
    tmp = base[:]  # mutable copy of identity
    for i in range(n):
        for j in range(i + 1, n):
            tmp[i], tmp[j] = tmp[j], tmp[i]
            s = ask(tmp)
            if s > B:                    # Δ > 0  -> adjacency between i and j
                adj[i].append(j)
                adj[j].append(i)
            tmp[i], tmp[j] = tmp[j], tmp[i]  # restore to identity

    # 3) Reconstruct the permutation.
    perm = [-1] * n
    used = [False] * n

    # Fixed points: degree 0
    for i in range(n):
        if len(adj[i]) == 0:
            perm[i] = i + 1
            used[i] = True

    # 2-cycles: degree 1
    for i in range(n):
        if not used[i] and len(adj[i]) == 1:
            j = adj[i][0]
            perm[i] = j + 1
            perm[j] = i + 1
            used[i] = used[j] = True

    # Cycles of length >= 3: degree 2
    for i in range(n):
        if used[i]:
            continue
        # Collect one undirected cycle in order
        cyc = []
        u = i
        prev = -1
        while True:
            cyc.append(u)
            used[u] = True
            a, b = adj[u][0], adj[u][1]   # degree 2, so exactly two neighbors
            v = a if a != prev else b
            prev, u = u, v
            if u == cyc[0]:
                break

        L = len(cyc)
        # 4) Determine orientation with one extra query:
        #    try mapping cyc[k] -> cyc[k+1]; if we gain L matches, that's the direction.
        test = base[:]  # identity elsewhere
        for k in range(L):
            test[cyc[k]] = cyc[(k + 1) % L] + 1
        res = ask(test)

        if res - B == L:
            # forward orientation is correct
            for k in range(L):
                perm[cyc[k]] = cyc[(k + 1) % L] + 1
        else:
            # reverse orientation
            for k in range(L):
                perm[cyc[k]] = cyc[(k - 1) % L] + 1

    # 5) Final answer
    ask(perm)

if __name__ == "__main__":
    main()

Problem C — One Way Only

Open the original problem on Kattis .

Strategy Guide & Solution

1. The Intuition

At first glance, this problem looks like it requires complex graph theory or a search algorithm (BFS/DFS). However, the constraints ($r, c \le 10^5$) suggest that an $\Theta(r \times c)$ simulation is too slow. We need a linear time solution $\Theta(r+c)$, which implies a Greedy approach.

The core insight lies in geometry. A preferred path cuts a rectangular grid into two distinct, non-overlapping regions:

The Upper-Right Region (Strictly above/right of the path).
The Lower-Left Region (Strictly below/left of the path).

Since hikers can only move Right and Down, they cannot cross from the Lower-Left region to the Upper-Right region (or vice versa) without crossing the preferred path itself. Therefore, we can solve the problem for these two regions independently and sum the results.

2. Deconstructing the Path logic

Let’s analyze how a hiker “cheats” (deviates from the preferred path).

The Upper-Right Deviation

In the Upper-Right region, a hiker deviates and rejoins the path under specific conditions:

The Deviation (Exit): The preferred path moves Down (D). This exposes a tile to the Right, allowing a hiker to slip into the upper region.
The Re-entry (Entrance): Later, the preferred path moves Right (R). This exposes a tile from Above, allowing the hiker to slip back onto the path.

Goal: We must break the connection between every “Exit” and its corresponding “Entrance”.

The Lower-Left Deviation

In the Lower-Left region, the logic is mirrored:

The Deviation (Exit): The preferred path moves Right (R). This exposes a tile Below, allowing a hiker to slip into the lower region.
The Re-entry (Entrance): Later, the preferred path moves Down (D). This exposes a tile to the Left, allowing the hiker to slip back onto the path.

3. The Algorithm: Greedy Matching (Parentheses Balancing)

We can model this problem exactly like the “Valid Parentheses” problem common in Data Structures courses.

Logic for Region 1 (Upper-Right)

We need to find how many times a D (Exit) is followed eventually by an R (Entrance).

Treat every D as an Open Parenthesis (.
Treat every R as a Closing Parenthesis ).
We iterate through the string. Every time we find a matching pair ( … ), it represents a valid detour that exists. To block it, we must place an ‘X’.
Action: Count the pairs. Each pair requires 1 X to block.

Logic for Region 2 (Lower-Left)

Treat every R as an Open Parenthesis (.
Treat every D as a Closing Parenthesis ).
Action: Count the pairs. Each pair requires 1 X.

Why “Greedy” works

Why don’t we need complex flow networks? Because the grid structure is linear along the path. The “earliest” available Exit will always connect to the “earliest” available Entrance. Blocking one tile effectively “consumes” one Exit/Entrance pair.

4. Step-by-Step Walkthrough

Input: RRDRD (Dimensions 3x4)

Step A: Analyze Upper-Right (Sources=`D`, Sinks=`R`)

R: Ignore.
R: Ignore.
D: Exit found. (Open connections: 1)
R: Re-entry found. We have an open connection!
- Action: Place an X (increment count).
- Update: Close the connection (Open connections: 0).
D: Exit found. (Open connections: 1)
End of string.

Region Result: 1 tile needed.

Step B: Analyze Lower-Left (Sources=`R`, Sinks=`D`)

R: Exit found. (Open connections: 1)
R: Exit found. (Open connections: 2)
D: Re-entry found.
- Action: Place an X (increment count).
- Update: Use one open connection (Open connections: 1).
R: Exit found. (Open connections: 2)
D: Re-entry found.
- Action: Place an X (increment count).
- Update: Use one open connection (Open connections: 1).
End of string.

Region Result: 2 tiles needed.

Total: $1 + 2 = 3$.

5. Complexity Analysis

Time Complexity: $\Theta(N)$, where $N = r + c - 2$. We iterate through the path string exactly twice (once for each region).
Space Complexity: $\Theta(N)$ to store the input string, or $\Theta(1)$ if reading character by character.

6. Python Solution

import sys

def solve():
    # Reading all input from stdin
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    # While r and c are provided, we primarily need the path string 's'
    # r = int(input_data[0])
    # c = int(input_data[1])
    s = input_data[2]

    total_x_needed = 0

    # --- Pass 1: Upper-Right Region ---
    # A detour is possible if we go Down (Exit) and later come back via Right (Entrance)
    # We treat 'D' as open '(' and 'R' as closed ')'
    balance = 0
    for char in s:
        if char == 'D':
            balance += 1       # Opened a potential detour
        elif char == 'R':
            if balance > 0:    # Closing a detour
                total_x_needed += 1
                balance -= 1   # We blocked this specific pair

    # --- Pass 2: Lower-Left Region ---
    # A detour is possible if we go Right (Exit) and later come back via Down (Entrance)
    # We treat 'R' as open '(' and 'D' as closed ')'
    balance = 0
    for char in s:
        if char == 'R':
            balance += 1       # Opened a potential detour
        elif char == 'D':
            if balance > 0:    # Closing a detour
                total_x_needed += 1
                balance -= 1   # We blocked this specific pair

    print(total_x_needed)

if __name__ == '__main__':
    solve()

Problem J — Game of Nines

Open the original problem on Kattis .

1. Story-style intuition

Picture your digits $0$–$8$ as tokens on a 10-hour clock (positions $0$ through $9$). When you “add digit $a$ to digit $b$”, you move token $b$ forward by $a$ ticks around the clock. If you land exactly on $9$, that token disappears.

Two important facts drive everything:

Helpers don’t get used up.

A digit you use as an adder stays on the table. You can reuse it indefinitely.
Only the total step size matters.

Adders are reusable and order doesn’t matter, so what matters is the set of step sizes you can produce in total modulo $10$.

We call this set of reusable digits the helper set $H$.

2. What is $d$?

Given a helper set $H$, the achievable total steps (mod $10$) are exactly the multiples of:

$$ d := \gcd\bigl(10,; \text{all digits in } H\bigr). $$

This is because the sums of helpers form a subgroup of $\mathbb{Z}_{10}$, and every subgroup is ${0,d,2d,\ldots,10-d}$ for some $d\in{1,2,5,10}$.

Interpretation: :math:`d` is your tick size around the circle.

$d=1$ → can move any number of steps
$d=2$ → even steps only
$d=5$ → only multiples of 5
$d=10$ → no movement possible

A token $b$ is eliminable iff:

$$ b \text{ is eliminable using } H \iff d \mid (9-b). $$

3. Everything reduces to one gcd

Take $H$ to be all digits you have. Define:

$$ g = \gcd(10, a_1, a_2, \dots, a_n). $$

If $g=1$, you can produce every step size → you can eliminate tokens until only one remains.
If $g\in{2,5,10}$, no $9-b$ is divisible by $g$, so nothing can be eliminated.

Thus:

$$ \text{Answer} = \begin{cases} 1 & \text{if } \gcd(10, a_1,\dots,a_n)=1,\[4pt] n & \text{otherwise.} \end{cases} $$

4. Constructive play when $g=1$

Case 1: You have a digit in ${1,3,7}$ (coprime with 10). Keep one; repeatedly add it to any other digit until that digit becomes $9$ and disappears.

Case 2: Otherwise, $g=1$ implies you have a $5$ and a nonzero even $e\in{2,4,6,8}$. Keep ${e,5}$ as helpers.

For a target $b$:

If $b$ is odd → eliminate using repeated $e$ moves.
If $b$ is even → apply $5$ once to make it odd, then finish with $e$.

You can also eliminate the $5$ using $e$ because $5 + ke \equiv 9 \pmod{10}$ always has a solution.

5. Short proof

Achievable totals form a subgroup of $\mathbb{Z}_{10}$ → equal to multiples of $d$.
$b$ is eliminable ⇔ $b+t\equiv9\pmod{10}$ for some achievable $t$ ⇔ $d\mid(9-b)$.
If $g=1$, all digits are eliminable; if $g\in{2,5,10}$, none are.
A move consumes two digits but removes at most one, so one token remaining is optimal.

6. Algorithm

Read $n$ and digits $a_i$.
Compute $g=\gcd(10,a_1,\ldots,a_n)$.
Output 1 if $g=1$, else $n$.

Time: $\Theta(n)$
Memory: $\Theta(1)$

7. Reference implementations

Python

import sys
import math

def solve():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    g = 10
    for i in range(1, n + 1):
        x = int(data[i])
        g = math.gcd(g, x)
    print(1 if g == 1 else n)

if __name__ == "__main__":
    solve()

8. Quick sanity checks

$2 3 6$ ⇒ $\gcd(10,2,3,6)=1$ ⇒ output 1
$4 4$ ⇒ $\gcd(10,4,4)=2$ ⇒ output 2
$0 5 5$ ⇒ $\gcd(10,0,5,5)=5$ ⇒ output 3
$2 5$ ⇒ $\gcd(10,2,5)=1$ ⇒ output 1

Back to the contest

2025 Southeast Regional Contest · 2026 Southeast Regional Contest