Ash Record

Platform: CACTF2026 | Category: Coding | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: prefix_subsequence_dp, minimal_timestamp_greedy, exchange_argument_optimality, timestamp_sorting, http_code_judge_automation

Summary

Task: narrative-wrapped algorithmic code-judge problem — find the longest prefix of an extraction sequence confirmable as a timestamp-ordered subsequence of residues with a minimum time gap between consecutive matches. Solution: O(N log N + N*P) DP tracking the minimal last-matched timestamp per prefix length (exchange-argument greedy), submitted to a Flask POST /run JSON judge to retrieve the flag.

Ash Record — CACTF2026

Description

Elowen Ashglass recovered residues across a site, each carrying an integer timestamp and a material type. She holds a suspected extraction sequence (list of material types in order). Find the LONGEST PREFIX of that sequence that can be confirmed as a subsequence of the residues in timestamp order, where no two consecutively matched residues are closer together in time than a minimum gap.

Formal I/O

• Line 1: N P min_gap
  • N = number of recovered residues (1 <= N <= 5000)
  • P = length of the suspected extraction sequence (1 <= P <= 12)
  • min_gap = minimum time difference required between two consecutively matched residues (1 <= min_gap <= 10)
• Line 2: P space-separated material-type strings (the extraction sequence, in order).
• Next N lines: each residue timestamp material_type (1 <= timestamp <= 10000; lowercase, length <= 10). Residues are not necessarily in timestamp order.
• Output: a single integer — the maximum number of consecutive steps from the beginning of the extraction sequence confirmable by a subsequence of residues satisfying the time-gap constraint. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Sample

5 4 3
ash rope oil ash
1 ash
4 rope
7 oil
10 ash
11 rope

Output: 4 — the full prefix ash rope oil ash matches residues at timestamps 1, 4, 7, 10 (each consecutive gap >= 3).

Recon

The stated target 154.57.164.67:32418 is not a raw interactive TCP service; plain netcat produced silence. It is a Flask/Werkzeug HTTP web app:

• GET / HTTP/1.0 returns Server: Werkzeug/3.1.3 Python/3.14.0, page title "Coding".
• The page ships a Monaco code editor and loads /static/js/prompts.js with per-language starter templates (python/c/cpp/rust).
• Submission API: POST /run with JSON body {"code": <source>, "language": "python"}.
• On a full pass the response is {"challengeCompleted":true,"flag":"HTB{...}","result":{}}; on failure result holds the failing test case. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So the challenge is a hidden-test code judge — solve the algorithm locally, then automate an HTTP submission.

Analysis

This is a constrained "longest matching prefix as an ordered subsequence" problem:

• We must match the extraction sequence from its start (target[0], target[1], ...), stopping at the first step that cannot be confirmed.
• Matches must respect timestamp order: since residues arrive unsorted, we first sort by timestamp.
• Between two consecutively matched residues the time difference must be >= min_gap. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The crucial structural fact is that P <= 12 is tiny, so we can carry a full DP state indexed by prefix length.

Key insight (exchange argument). For a fixed confirmed prefix length k, the only thing the future cares about is the timestamp of the last matched residue, because the next match t' only needs t' - last >= min_gap. A smaller last timestamp is never worse — it can only make future gap constraints easier to satisfy. Therefore, for each k, it is optimal to track the minimal achievable last-matched timestamp. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

This collapses the state to a single value per prefix length: best[k] = minimal possible last-matched timestamp that confirms exactly k prefix steps.

Solution

DP over prefix positions, O(N log N + N*P):

1. Sort residues by timestamp ascending.
2. Init best[0] = -infinity (zero steps, no timing constraint); all best[k>0] = +infinity.
3. Process each residue (t, type) in timestamp order. Iterate k from P-1 down to 0:
   • if best[k] is finite, type == target[k], and t - best[k] >= min_gap, then relax best[k+1] = min(best[k+1], t).
4. Answer = the largest k with finite best[k]. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Correctness notes

• Optimality: the exchange argument above justifies minimizing best[k]; any locally better last timestamp dominates.
• No self-chaining within one residue: iterating k in descending order means a residue that relaxes best[k+1] is not re-read at best[k] in the same pass.
• Equal-timestamp residues cannot chain to each other: their gap would be 0 < min_gap (since min_gap >= 1), and the t - best[k] >= min_gap test rejects it.
• Validity: every finite best[k] is realized by an actual valid subsequence of length k. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solve script

 python read-only • copy allowed Copy
import sys

def main():
    data = sys.stdin.read().split('\n')
    idx = 0
    first = data[idx].split(); idx += 1
    N, P, min_gap = int(first[0]), int(first[1]), int(first[2])
    target = data[idx].split(); idx += 1
    res = []
    for _ in range(N):
        parts = data[idx].split(); idx += 1
        t = int(parts[0]); typ = parts[1]
        res.append((t, typ))
    res.sort(key=lambda x: x[0])

    INF = float('inf')
    best = [INF] * (P + 1)
    best[0] = -INF
    ans = 0
    for t, typ in res:
        for k in range(P - 1, -1, -1):
            if best[k] == INF:
                continue
            if typ == target[k] and t - best[k] >= min_gap:
                if t < best[k + 1]:
                    best[k + 1] = t
                    if k + 1 > ans:
                        ans = k + 1
    print(ans)
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

main()

Automated submission to the code judge

 python read-only • copy allowed Copy
import json, urllib.request
code = open('sol.py').read()
body = json.dumps({'code': code, 'language': 'python'}).encode()
req = urllib.request.Request(
    'http://154.57.164.67:32418/run',
    data=body,
    headers={'Content-Type': 'application/json'},
)
print(urllib.request.urlopen(req, timeout=60).read().decode())

The submission passed all hidden tests on the first try, and the JSON response returned challengeCompleted: true with the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍