Back From Where

Flag: scriptCTF{d0nt_u_ju5t_!@ve_z%ro3s???_64dff2564e51}

TL;DR

We solved a 100×100 grid DP where you move only right or down from the top-left and multiply all numbers along the path. For every cell, output the maximum trailing zeros achievable upon arriving at that cell. Trailing zeros = min(total_2s, total_5s).

To compute it efficiently, we maintain at each cell a Pareto frontier of (sum2, sum5) pairs (non-dominated under coordinate-wise ≥). Merge frontiers from top and left, add the current cell’s (c2, c5), then prune with proper dominance. Our initial pruning was wrong; fixing the skyline rule made the solution accepted.

Challenge

Server: nc play.scriptsorcerers.xyz 10101

Given: The server prints a 100×100 grid of integers (each is even or a multiple of 5).

Task: For each grid cell (i,j), output the maximum number of trailing zeros achievable on any start→(i,j) right/down path.

Judge flow (from server.py):
- Generates grid
- Runs their reference ./solve on the grid
- Reads your 100 lines
- Compares exact equality and prints the flag if all match
- Time limit: 20 seconds

Note: The prompt mentions “BackFromBrazil (n00bzctf 2024)”. Similar idea, but here we must output a value for every node, not just the destination.

Math & Key Insight

Trailing zeros of a product are min(v2(product), v5(product)).

For each cell value x, precompute c2 = v2(x), c5 = v5(x).

If you only kept a single scalar DP (e.g., max sum2 or max sum5), you’d lose optimal trade-offs. We need to keep a set of possible (sum2, sum5) states that are not dominated.

Pareto Frontier

A pair (a1, b1) dominates (a2, b2) if a1 ≥ a2 and b1 ≥ b2 and at least one strict. For maximizing min(a, b) with nonnegative additions, dominated states can be safely dropped.

Correct prune:

Coalesce by a, keeping the max b for that a.

Sort by a descending.

Sweep, keeping only entries with b strictly increasing as a decreases (i.e., discard any (a, b) with b ≤ max_b_seen).

(Optional) Re-sort by a ascending for nicer iteration.

Our initial (wrong) prune kept b increasing with a ascending. Counterexample: keeping (1,5) and dropping (2,5) kills the optimum since min(2,5) > min(1,5).

Algorithm

For each cell (i, j) in row-major order:

Let F_top = frontier at (i-1, j) (if exists), F_left = frontier at (i, j-1) (if exists).

Build candidates = {(a+c2[i][j], b+c5[i][j]) for (a,b) in F_top ∪ F_left}. If no parents, candidates = {(c2,c5)}.

frontier[i][j] = prune(candidates) with the correct dominance rule.

Answer at (i,j) is max(min(a,b) for (a,b) in frontier[i][j]).

Complexity: Frontier sizes remain modest in random grids (avg ~20–60). Overall about O(N^2 * K) merges/prunes; Python runs in well under the 20s TL.

Implementation Details

Count exponents:

def vcnt(x, p):
    c = 0
    while x % p == 0:
        x //= p
        c += 1
    return c

Correct frontier pruning (coordinate-wise dominance):

def prune_frontier(pairs):
    if not pairs:
        return []
    best_for_a = {}
    for a, b in pairs:
        if b > best_for_a.get(a, -1):
            best_for_a[a] = b
    items = sorted(best_for_a.items(), key=lambda t: -t[0])  # a desc
    res, max_b = [], -1
    for a, b in items:
        if b > max_b:
            res.append((a, b))
            max_b = b
    res.sort()  # a asc
    return res

Frontier DP + per-cell answer:

# F[i][j] is a list of (sum2, sum5)
F = [[None]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        base2, base5 = c2[i][j], c5[i][j]
        cand = []
        if i > 0:
            cand += [(a+base2, b+base5) for (a,b) in F[i-1][j]]
        if j > 0:
            cand += [(a+base2, b+base5) for (a,b) in F[i][j-1]]
        if not cand:
            cand = [(base2, base5)]
        F[i][j] = prune_frontier(cand)
        A[i][j] = max(min(a,b) for a,b in F[i][j])

Final Working Client (Start→Cell)

import socket, sys, time
from statistics import mean

HOST = "play.scriptsorcerers.xyz"
PORT = 10101
N = 100

VERBOSE = True
SHOW_GRID_HEAD = 5
SHOW_SAMPLE_CELLS = [(0,0), (0, N-1), (N-1,0), (N-1,N-1), (N//2, N//2)]

def vcnt(x, p):
    c = 0
    while x % p == 0:
        x //= p
        c += 1
    return c

def prune_frontier(pairs):
    if not pairs:
        return []
    best_for_a = {}
    for a, b in pairs:
        if b > best_for_a.get(a, -1):
            best_for_a[a] = b
    items = sorted(best_for_a.items(), key=lambda t: -t[0])  # a desc
    res, max_b = [], -1
    for a, b in items:
        if b > max_b:
            res.append((a, b))
            max_b = b
    res.sort()  # a asc
    return res

def read_grid(s_file, n):
    grid = []
    while len(grid) < n:
        line = s_file.readline()
        if not line:
            raise RuntimeError("Connection closed before grid finished")
        parts = line.strip().split()
        try:
            nums = list(map(int, parts))
        except ValueError:
            continue
        if len(nums) == n:
            grid.append(nums)
    return grid

def main():
    with socket.create_connection((HOST, PORT)) as s:
        s_file = s.makefile("rwb", buffering=0)
        grid = read_grid(s_file, N)

        c2 = [[vcnt(grid[i][j], 2) for j in range(N)] for i in range(N)]
        c5 = [[vcnt(grid[i][j], 5) for j in range(N)] for i in range(N)]

        t0 = time.perf_counter()
        F = [[None]*N for _ in range(N)]
        A = [[0]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                base2, base5 = c2[i][j], c5[i][j]
                cand = []
                if i > 0:
                    cand += [(a+base2, b+base5) for (a,b) in F[i-1][j]]
                if j > 0:
                    cand += [(a+base2, b+base5) for (a,b) in F[i][j-1]]
                if not cand:
                    cand = [(base2, base5)]
                F[i][j] = prune_frontier(cand)
                A[i][j] = max(min(a,b) for a,b in F[i][j])
        t1 = time.perf_counter()

        # Optionally print some debug (safe under TL)
        if VERBOSE:
            print(f"[TIMINGS] forward DP: {(t1-t0):.4f}s")
            k = SHOW_GRID_HEAD
            print("\n[ANS start→cell top-left]")
            for i in range(k):
                print(" ".join(str(A[i][j]) for j in range(k)))

        # Send answers
        for i in range(N):
            s_file.write((" ".join(map(str, A[i])) + "\n").encode())
        s_file.flush()

        # Server response (flag/WA/TLE)
        try:
            while True:
                line = s_file.readline()
                if not line:
                    break
                sys.stdout.write(line.decode())
        except Exception:
            pass

if __name__ == "__main__":
    main()

Debugging Journey (What we tried)

Pass-through view (best start→cell→end via that cell). Looked plausible, but the judge returned WA.

Suffix-only view (best cell→end). Also WA.

Start→cell view with incorrect skyline: WA.

Start→cell view with correct skyline (coordinate-wise dominance): ACCEPTED ✅ and printed the flag.

Key Pitfall

Pruning with the wrong monotonic sweep can remove optimal states. Always use coordinate-wise dominance for the min() objective with nonnegative additions.

Sanity Checks We Used

A[0][0] == min(c2[0][0], c5[0][0]).

A[i][j] >= max(A[i-1][j], A[i][j-1]) is not guaranteed (because min can go down when you trade 2s for 5s), but along an optimal path to (i,j), values are nondecreasing.

Global best at (n-1,n-1) matches expectations and is never exceeded by any “pass-through” attempt.

Performance Notes

Frontier sizes averaged ~20–60 in our runs; max ~130 in worst cells of random grids.

End-to-end (including IO) comfortably inside the 20s TL; DP itself is sub-second to a few seconds in Python.

Takeaways

When the objective is min(sum2, sum5) and additions are nonnegative, you must keep the full Pareto frontier under coordinate-wise dominance.

Be explicit about the problem interpretation: per-node prefix (start→cell) was the judge’s expected output here.

Add quick local sanity tests and debugging prints; they pay off immediately when a judge says WA.