CUSTOMMediumCoding

Rumour Spine

XESXOR9/2/20266 min read

#coding#custom#medium#node_splitting#max_flow_min_cut#dinic_algorithm#min_vertex_cut#narrative_to_algorithm#linux

Rumour Spine

Platform: CACTF2026 | Category: Coding | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: node_splitting, max_flow_min_cut, dinic_algorithm, min_vertex_cut, narrative_to_algorithm

Summary

Task: coding challenge on a Flask/Werkzeug judge asking for the minimum number of intermediate nodes to remove to disconnect a directed source from a sink. Solution: recognize it as minimum s-t vertex cut, solve via Menger's theorem with node-splitting max-flow (Dinic's), submit through POST /run.

Rumour Spine — CACTF2026

Description

Suncourt doesn't march first — it primes first. Miren Vale has traced the Quiet March's invitation chain: a coordinator who never touches ash, only schedules, feeding a priming signal through a network of quiet hands — candle-buyers, shrine-attendants, penitent-scribes — until a target district falls still the night before the March arrives. Every hand who passes the signal on is a link Miren can expose. Miren means to break the chain before the district goes quiet. She can expose any quiet hand along the way — one flagged, one route burned, at the cost of one favour she can never call in again. The coordinator and the target district can't be touched directly: too visible, too soon. What is the minimum number of quiet hands that must be exposed to sever every path the priming signal could still travel? ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

English summary: A Flask/Werkzeug-hosted coding challenge. Given a directed graph with a fixed source node S (the coordinator) and sink node T (the target district), compute the minimum number of intermediate nodes (any node other than S and T) that must be removed so that no path from S to T remains. The solution source is submitted to a judge via a JSON API and, on passing all tests, the platform returns the flag.

Semantic Clue: Translating the Narrative into an Algorithm

The narrative is a direct encoding of a graph-theory primitive: ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

"network of quiet hands" who "pass the signal on" → nodes of a directed graph.
"invitation chain" / "a link" → directed edges (u passes to v).
"coordinator" (never touches ash, only schedules) → source S, cannot be touched.
"target district" → sink T, cannot be touched.
"expose any quiet hand ... one route burned" → removing an intermediate vertex.
"The coordinator and the target district can't be touched directly" → S and T are not removable.
"minimum number of quiet hands that must be exposed to sever every path" → minimum s-t vertex cut. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

So the whole story is the classic minimum s-t vertex cut problem: the fewest intermediate vertices whose deletion disconnects S from T.

Analysis

Formal statement from the platform:

Line 1: N E S T (nodes, edges, source, sink). Always S = 0, T = N-1.
Next E lines: directed edge u v.
Output: single integer = minimum number of intermediate vertices to remove to disconnect S→T.
Constraints: 6 <= N <= 120, 1 <= E <= 360, graph may contain cycles, at least one S→T path exists, and there is no direct edge S→T (which guarantees a finite vertex cut exists — a direct edge would make it impossible to cut using intermediate vertices only). ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Why not a single articulation node?

The worked example shows the four disjoint paths 0->1->3->6, 0->1->4->6, 0->2->3->6, 0->2->4->6. No single node is on every path, but the pair {1, 2} covers them all → answer 2. This is precisely why a simple dominator/articulation approach is insufficient and a true min-cut is needed.

The theorem

By Menger's theorem (vertex version): the minimum number of internal vertices separating S from T equals the maximum number of internally vertex-disjoint S→T paths. We compute that maximum via a max-flow reduction with node splitting. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Solution

Node-splitting reduction (standard vertex-capacity trick):

Split each node i into i_in = 2*i and i_out = 2*i+1.
Add an internal edge i_in -> i_out:
- capacity 1 for every removable node (all except S and T),
- capacity INF for S and T (they cannot be removed).
For each original directed edge u -> v, add u_out -> v_in with capacity INF (edges are free; only vertices are cut).
Set flow source = S_out = 2*S+1, flow sink = T_in = 2*T.
Run Dinic's algorithm. The resulting max flow = min s-t vertex cut = the answer. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Because each removable node's internal edge has capacity 1 and original edges are infinite, every min cut must saturate node-internal edges, so the cut value equals a count of vertices — exactly the number of quiet hands to expose.

Recon / platform mechanics

Raw netcat sent nothing back; a plain line triggered a 400 "Bad request syntax", revealing an HTTP service.
curl http://HOST:PORT/ returned an HTML "Coding" page with a Monaco editor; Server: Werkzeug/3.1.3 Python/3.14.0. The problem statement, constraints, and worked example are embedded in the page HTML.
Submission API: POST /run with JSON {"code": <source>, "language": "python|c|cpp|rust"}.
Success response: {"challengeCompleted": true, "flag": "...", "result": {}}. Failure returns failing test-case details in result.
The starter templates in /static/js/prompts.js only read a single number, but the real judge feeds the full graph on stdin — read all of stdin. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Solver

 python read-only • copy allowed
import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    idx = 0
    N = int(data[idx]); idx+=1
    E = int(data[idx]); idx+=1
    S = int(data[idx]); idx+=1
    T = int(data[idx]); idx+=1
    edges = []
    for _ in range(E):
        u = int(data[idx]); idx+=1
        v = int(data[idx]); idx+=1
        edges.append((u,v))

    V = 2*N
    INF = 10**9
    graph = [[] for _ in range(V)]
    def add(a,b,c):
        graph[a].append([b,c,len(graph[b])])
        graph[b].append([a,0,len(graph[a])-1])
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    # Node splitting: internal edge capacity 1 (removable) or INF (S/T, not removable)
    for i in range(N):
        cap = INF if (i==S or i==T) else 1
        add(2*i, 2*i+1, cap)
    # Original directed edges are free (INF): u_out -> v_in
    for (u,v) in edges:
        add(2*u+1, 2*v, INF)

    src = 2*S+1   # S_out
    snk = 2*T     # T_in

    def bfs():
        level = [-1]*V
        level[src]=0
        q=deque([src])
        while q:
            u=q.popleft()
            for e in graph[u]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]]=level[u]+1
                    q.append(e[0])
        return level
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    def dfs(u,f,level,it):
        if u==snk: return f
        while it[u]<len(graph[u]):
            e=graph[u][it[u]]
            if e[1]>0 and level[e[0]]==level[u]+1:
                d=dfs(e[0],min(f,e[1]),level,it)
                if d>0:
                    e[1]-=d
                    graph[e[0]][e[2]][1]+=d
                    return d
            it[u]+=1
        return 0

    # Dinic's algorithm
    flow=0
    while True:
        level=bfs()
        if level[snk]<0: break
        it=[0]*V
        while True:
            f=dfs(src,INF,level,it)
            if f==0: break
            flow+=f
    print(flow)
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

main()

Verified: prints 2 on the worked example and was accepted by the judge on all hidden tests.

Submission

 bash read-only • copy allowed
curl -s http://154.57.164.70:31792/run \
  -H 'Content-Type: application/json' \
  --data-binary @<(python3 -c 'import json,sys;print(json.dumps({"code":open("solution.py").read(),"language":"python"}))')

Response: {"challengeCompleted":true,"flag":"HTB{REDACTED}","result":{}}. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍