CUSTOMMediumCoding

Vow Engine

XESXOR9/2/20265 min read

#coding#custom#medium#xor_path_basis#gf2_gaussian_elimination#cycle_space_basis#connected_components_dfs#spanning_tree_xor#linux

Vow Engine

Platform: CACTF2026 | Category: Coding | Type: Challenge | Difficulty: Medium | OS: Linux | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: xor_path_basis, gf2_gaussian_elimination, cycle_space_basis, connected_components_dfs, spanning_tree_xor

Summary

Task: coding-judge challenge asking whether an XOR cadence value T is achievable on any path between two nodes in an undirected weighted graph with cycles. Solution: build spanning-tree xor_to_root plus a GF(2) linear basis of the cycle space per component, then check if xor_to_root[u]^xor_to_root[v]^T reduces to 0 in the basis.

Vow Engine — CACTF2026

Description

"Vow Engine": A network of witnesses (nodes) linked by seal-marks (undirected edges), each edge carrying a cadence key (weight w). The "weight" of an oath passed along a path = the XOR of every edge weight along the path from speaker to witness. Because the graph has redundant links (cycles), a pair of witnesses can be connected by more than one path, and different paths yield different XOR values. For each of Q queries (u, v, T), answer YES/NO: is cadence value T achievable on ANY oath-path between witnesses u and v? ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

English summary: Given an undirected weighted graph, for each query (u, v, T) decide whether some walk/path between u and v has edge-weight XOR equal to T. Answer YES/NO per query.

Input format:

Line 1: N M Q (nodes 0..N-1, edges, queries)
Next M lines: u v w (undirected edge with weight w)
Next Q lines: u v T (query)

Sample input:

Sample output:

YES
NO
YES
NO

Analysis

This is the classic "XOR path between two nodes in an undirected weighted graph" problem, solved with a GF(2) linear (cycle-space) basis. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Key theory. The set of all achievable path-XOR values between u and v (within one connected component) equals:

base ⊕ span(cycle space of the component)

where:

base = xor_to_root[u] ^ xor_to_root[v] — the XOR along the spanning-tree path between u and v.
the cycle space is generated by the XOR value of every fundamental cycle.

Why: any walk between u and v differs from the tree path by a set of cycles; XOR-ing in any fundamental cycle is a legal transformation (you can always detour around a cycle since walks may repeat edges). So T is achievable iff T ^ base lies in the linear span (over GF(2)) of the cycle values, i.e. iff xor_to_root[u] ^ xor_to_root[v] ^ T reduces to 0 under the component's basis. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Sample verification (query 3, (0,1,15)):

Tree path 0->1 gives base = 3.
Cycle 0-1(3), 1-2(5), 0-2(10) has XOR 3^5^10 = 12.
3 ^ 12 = 15 → YES (matches path 0->2->1 = 10^5 = 15).

Solution

Algorithm:

Build an adjacency list. Each undirected edge is stored twice.
For each connected component, run an iterative DFS computing xor_to_root[v] (XOR of weights from a chosen root to v).
For every non-tree edge inside a component, compute the cycle value cyc = xor_to_root[u] ^ xor_to_root[v] ^ w. If nonzero, insert it into that component's GF(2) linear basis (Gaussian elimination over bits). The duplicated storage yields a trivial cycle w^w=0, naturally skipped by the if cyc check.
For a query (u, v, T): if u, v are in different components → NO. Otherwise reduce x = xor_to_root[u] ^ xor_to_root[v] ^ T by the component basis; answer YES iff it reduces to 0. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Delivery / platform mechanics

The target looked like a raw TCP service but is actually an HTTP coding-judge (Flask/Werkzeug 3.1.3, Python 3.14). Raw nc line probes returned HTTP 400 Bad request syntax.

Submit the solution as an HTTP POST:

 bash read-only • copy allowed
curl -s http://154.57.164.65:31763/run \
  -H 'Content-Type: application/json' \
  --data-binary @payload.json
# payload.json = {"code": "<source>", "language": "python"}

On success the JSON response contains {"challengeCompleted": true, "flag": "HTB{...}"}. On failure it returns a failed test-case object. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

Solve script (submitted source)

 python read-only • copy allowed
import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx+=1
    m = int(data[idx]); idx+=1
    q = int(data[idx]); idx+=1

    head = [-1]*n
    nxt = [0]*(2*m)
    to = [0]*(2*m)
    wt = [0]*(2*m)
    ec = 0
    for _ in range(m):
        u = int(data[idx]); v = int(data[idx+1]); w = int(data[idx+2]); idx+=3
        to[ec]=v; wt[ec]=w; nxt[ec]=head[u]; head[u]=ec; ec+=1
        to[ec]=u; wt[ec]=w; nxt[ec]=head[v]; head[v]=ec; ec+=1
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    xor_to_root = [0]*n
    comp = [-1]*n
    comp_basis = []
    visited = [False]*n

    for s in range(n):
        if visited[s]:
            continue
        cid = len(comp_basis)
        basis = []
        comp_basis.append(basis)
        stack = [s]
        visited[s] = True
        xor_to_root[s] = 0
        comp[s] = cid
        while stack:
            u = stack.pop()
            e = head[u]
            while e != -1:
                v = to[e]; w = wt[e]
                if not visited[v]:
                    visited[v] = True
                    xor_to_root[v] = xor_to_root[u] ^ w
                    comp[v] = cid
                    stack.append(v)
                else:
                    cyc = xor_to_root[u] ^ xor_to_root[v] ^ w
                    if cyc:
                        x = cyc
                        for b in basis:
                            x = min(x, x ^ b)
                        if x:
                            basis.append(x)
                            basis.sort(reverse=True)
                e = nxt[e]
‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍

    out = []
    for _ in range(q):
        u = int(data[idx]); v = int(data[idx+1]); t = int(data[idx+2]); idx+=3
        if comp[u] != comp[v]:
            out.append("NO")
            continue
        x = xor_to_root[u] ^ xor_to_root[v] ^ t
        for b in comp_basis[comp[u]]:
            x = min(x, x ^ b)
        out.append("YES" if x == 0 else "NO")

    sys.stdout.write("\n".join(out) + ("\n" if out else ""))

main()

Submitting this source through /run passes every judge test and returns the flag. ‍‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‍