Mr. Worldwide — MetaCTF

Description

Please help! I'm a tour guide, and I need to tell my clients the minimum number of miles they need to travel to different cities to reach all their goals. They're really on me, so you have to do it FAST! The first number given is the number of nodes in the graph, and the rest of the numbers is an adjacency matrix of the graph, where each index represents the distance between the 2 correspondings nodes of the graph.

The service at nc nc.umbccd.net 23456 sends n = 20, then a 20 x 20 weighted adjacency matrix, and finally prompts for the minimum tour distance. The matrix is different on each connection, so the solve must parse the fresh instance and answer immediately.

One note worth preserving: the challenge was tracked locally under MetaCTF, but the returned flag used a DawgCTF format. I kept the event metadata as metactf to match the workspace and existing notes, and recorded the flag exactly as returned by the service.

Analysis

The keywords tour, cities, and adjacency matrix are the giveaway. This is a minimum Hamiltonian cycle problem: start at a city, visit every city exactly once, and return to the start with minimum total cost.

Because the graph is given as a complete weighted adjacency matrix and the prompt asks for the minimum tour distance, this is the classic Traveling Salesman Problem rather than a shortest-path or MST task.

The important parameters were:

• n = 20
• full weighted adjacency matrix
• remote instance changes every connection
• strict time limit

That size is the real constraint. Brute force over all tours is impossible, and a naive Python Held-Karp implementation was still too slow for the service, which responded with Time limit exceeded! Invalid input!.

The reason Python struggled is that Held-Karp for n = 20 still performs on the order of O(n^2 * 2^(n-1)) work. That is feasible in a compiled language with tight loops and flat arrays, but expensive in Python because of interpreter overhead, dictionary/list handling, and the large number of DP state transitions.

Solution

Why Held-Karp fits here

For TSP with n = 20, the standard exact approach is Held-Karp dynamic programming with bitmasks.

Define:

• dp[mask][j] = minimum cost to start at node 0, visit the subset mask over nodes 1..n-1, and finish at node j

Base case:

• dp[1 << (j - 1)][j] = dist[0][j]

Transition:

• dp[mask][j] = min(dp[mask without j][k] + dist[k][j])

Final answer:

• min_j dp[full_mask][j] + dist[j][0]

This gives exact TSP in O(n^2 * 2^(n-1)) time and O(n * 2^(n-1)) memory, which is just within range for n = 20 if implemented efficiently.

Why the fast version worked

The successful solve split the job in two parts:

1. A Python wrapper connected to the socket, parsed the latest matrix block, and handled sending the answer.
2. A compiled C++ solver performed the DP.

This avoids trying to do millions of DP transitions inside Python. The C++ code uses:

• std::vector<int> for flat contiguous storage
• bitmasks over nodes 1..n-1
• __builtin_ctz to iterate set bits efficiently
• fast I/O setup with std::ios::sync_with_stdio(false) and cin.tie(nullptr)

The service returned the flag after the first solved round.

Automation approach

The Python wrapper:

• connects to nc.umbccd.net:23456
• reads until Enter minimum tour distance:
• extracts the latest n + adjacency matrix block from the server output
• passes that block to the compiled solver via subprocess.check_output
• sends the computed answer back over the socket
• scans all received data for a flag-shaped string

This is a good pattern when the challenge needs both flexible protocol parsing and a very fast compute core.

Full working wrapper

#!/usr/bin/env python3
import re
import socket
import subprocess
from pathlib import Path


HOST = "nc.umbccd.net"
PORT = 23456
PROMPT = b"Enter minimum tour distance:"
FLAG_RE = re.compile(r"[A-Za-z0-9_]+\{[^\r\n}]+\}")
SOLVER = Path(__file__).with_name("tsp_solver")


def extract_matrix_block(text: str) -> str:
    lines = [line.strip() for line in text.splitlines() if line.strip()]
    for i in range(len(lines) - 1, -1, -1):
        if not re.fullmatch(r"\d+", lines[i]):
            continue
        n = int(lines[i])
        if i + n >= len(lines):
            continue
        ok = True
        for j in range(1, n + 1):
            row = lines[i + j].split()
            if len(row) != n or any(not re.fullmatch(r"\d+", x) for x in row):
                ok = False
                break
        if ok:
            return "\n".join(lines[i : i + n + 1]) + "\n"
    raise ValueError("Could not find adjacency matrix in server output")


def solve_block(block: str) -> int:
    out = subprocess.check_output([str(SOLVER)], input=block.encode())
    return int(out.strip())


def main() -> None:
    with socket.create_connection((HOST, PORT), timeout=10) as sock:
        sock.settimeout(10)
        buf = b""
        round_no = 0

        while True:
            try:
                chunk = sock.recv(65536)
            except socket.timeout:
                break

            if not chunk:
                break

            buf += chunk
            decoded = buf.decode("utf-8", "replace")
            flag_match = FLAG_RE.search(decoded)
            if flag_match:
                print(flag_match.group(0))
                return

            while PROMPT in buf:
                before, buf = buf.split(PROMPT, 1)
                text = before.decode("utf-8", "replace")
                block = extract_matrix_block(text)
                answer = solve_block(block)
                round_no += 1
                print(f"[+] round {round_no}: {answer}", flush=True)
                sock.sendall(f"{answer}\n".encode())

                decoded_buf = buf.decode("utf-8", "replace")
                flag_match = FLAG_RE.search(decoded_buf)
                if flag_match:
                    print(flag_match.group(0))
                    return

        decoded = buf.decode("utf-8", "replace")
        flag_match = FLAG_RE.search(decoded)
        if flag_match:
            print(flag_match.group(0))
        else:
            print(decoded)


if __name__ == "__main__":
    main()

Full working Held-Karp solver

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <limits>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) {
        return 1;
    }

    std::vector<int> w(n * n);
    for (int i = 0; i < n * n; ++i) {
        std::cin >> w[i];
    }

    if (n <= 1) {
        std::cout << 0 << '\n';
        return 0;
    }

    const int m = n - 1;
    const int subset_count = 1 << m;
    const int INF = std::numeric_limits<int>::max() / 4;

    std::vector<int> dp(static_cast<std::size_t>(subset_count) * n, INF);

    for (int j = 1; j < n; ++j) {
        dp[(1 << (j - 1)) * n + j] = w[j];
    }

    for (int mask = 1; mask < subset_count; ++mask) {
        int bits = mask;
        while (bits) {
            const int end_bit = bits & -bits;
            const int end_idx = __builtin_ctz(end_bit);
            const int end_node = end_idx + 1;
            const int prev_mask = mask ^ end_bit;
            int &best = dp[mask * n + end_node];

            if (prev_mask) {
                best = INF;
                int prev_bits = prev_mask;
                while (prev_bits) {
                    const int prev_bit = prev_bits & -prev_bits;
                    const int prev_idx = __builtin_ctz(prev_bit);
                    const int prev_node = prev_idx + 1;
                    const int prev_cost = dp[prev_mask * n + prev_node];
                    const int cand = prev_cost + w[prev_node * n + end_node];
                    if (cand < best) {
                        best = cand;
                    }
                    prev_bits ^= prev_bit;
                }
            }

            bits ^= end_bit;
        }
    }

    const int full_mask = subset_count - 1;
    int answer = INF;
    for (int j = 1; j < n; ++j) {
        const int cand = dp[full_mask * n + j] + w[j * n];
        if (cand < answer) {
            answer = cand;
        }
    }

    std::cout << answer << '\n';
    return 0;
}

Compile and run

g++ -O3 -std=c++17 tsp_solver.cpp -o tsp_solver
python3 solve.py