Toll Schedule

Platform: CACTF2026 | Category: Coding | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-27 | Status: Solved Techniques: ordered_matching, greedy_exchange_argument, max_heap_scheduling

Summary

Task: Assign convoys to distinct clearance openings no earlier than their arrivals while minimizing total wait. Solution: Sort both timelines, consume the earliest usable openings, and match each with the latest eligible arrival using a max-heap.

Toll Schedule — CACTF2026

Description

Stonepass doesn't close for weather anymore. It closes on words borrowed from weather — "raiders," "avalanches," "public order" — while the schedule underneath keeps quietly playing favourites: one banner's convoys glide through, another's stack up in the snow until daylight dies. Elric Ashspar has spent weeks sketching the checkpoint's hardware and is certain of one thing — the mechanism isn't broken. It's tuned.

To prove it, Elric first needs the number nobody at the gate wants published: the least total time this exact column of convoys could possibly spend waiting, under any legal assignment of clearances to convoys. Each convoy reaches the pass at a known time; each clearance opens at a known time and can seat exactly one convoy, no earlier than its arrival. Elric must find the assignment that minimises the column's total wait — the clean baseline the real schedule will be measured against.

The first line contains two space-separated integers: N and G. N is the number of convoys. G is the number of available checkpoint clearances (G >= N).

The second line contains N space-separated integers: the arrival time of each convoy (in any order).

The third line contains G space-separated integers: the opening time of each checkpoint clearance (in any order).

A convoy may only be assigned to a clearance that opens at or after the convoy's arrival time. Each convoy must be assigned to exactly one clearance. Each clearance can handle at most one convoy. It is guaranteed that a valid assignment exists.

Print a single integer: the minimum total waiting time across all convoys, where the waiting time for a convoy is its clearance's opening time minus the convoy's arrival time.

1 <= N <= 1200 N <= G <= 1500 1 <= arrival time <= 200 1 <= clearance opening time <= 220 It is guaranteed that every convoy can be assigned to a distinct clearance. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The input gives convoy arrival times and one-use clearance opening times. We must choose a distinct opening at or after each arrival and minimize the sum of all waits.

Analysis

Let convoy arrivals be a_i and their assigned openings be g_i. The objective is

 text read-only • copy allowed Copy
sum(g_i - a_i) = sum(selected openings) - sum(all arrivals).

The second term is fixed. Therefore, the actual optimization problem is to choose a feasible set of N openings with the smallest possible sum.

Sort both lists and scan openings from earliest to latest. Before considering an opening, add every unassigned convoy that has already arrived to a max-heap. If the heap is nonempty, consume this opening and assign it to the latest eligible arrival. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Why consuming the earliest usable opening is safe

Consider the first opening t that the greedy algorithm consumes. Take any feasible completion of the current partial assignment.

• If that completion skips t, the convoy selected by the greedy algorithm must be assigned to some later opening s. Moving it from s to t remains feasible and can only decrease the selected-opening sum.
• If the completion uses t for another eligible convoy b, while the greedy choice a is assigned later at s, swap the assignments. Since both were eligible at t, a -> t is legal; because b <= t <= s, b -> s is also legal. The selected opening set and cost do not change. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Thus an optimum exists that agrees with consuming t. Repeating the argument proves that greedily taking every usable opening produces the lexicographically earliest feasible set of openings, hence the minimum-sum set.

Why the latest eligible convoy is safe

The max-heap chooses the eligible convoy with the greatest arrival time. In the exchange above, replacing the convoy at the current opening cannot hurt future feasibility: the displaced convoy arrived no later than the chosen convoy, so it is also eligible for every later opening that could serve the chosen one. This ordered-neighborhood property is exactly what makes the exchange valid. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Consequently, no Hungarian algorithm or min-cost max-flow model is required. Those general algorithms would solve the bipartite assignment problem, but the nested feasible sets induced by time ordering and the linear objective reduce it to a greedy scan.

Solution

1. Sort arrivals and clearance openings.
2. Scan openings in ascending order.
3. Push all not-yet-considered arrivals at or before the current opening into a max-heap, represented by negated values in Python.
4. If the heap is nonempty, pop the latest eligible arrival and add opening - arrival to the answer.
5. Stop after assigning all N convoys. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The sample assigns arrivals 2, 4, 6, 9 to openings 3, 5, 8, 11, yielding total wait 1 + 1 + 2 + 2 = 6.

Accepted solver

 python read-only • copy allowed Copy
import heapq
import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, g = data[0], data[1]
    arrivals = sorted(data[2:2 + n])
    openings = sorted(data[2 + n:2 + n + g])

    # At each opening, use it whenever at least one convoy has arrived.
    # Choosing the latest such arrival is a safe ordered matching; accepting
    # the current opening minimizes the sum of selected opening times.
    available = []
    i = 0
    total = 0
    assigned = 0
    for opening in openings:
        while i < n and arrivals[i] <= opening:
            heapq.heappush(available, -arrivals[i])
            i += 1
        if available:
            arrival = -heapq.heappop(available)
            total += opening - arrival
            assigned += 1
            if assigned == n:
                break
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    print(total)


if __name__ == "__main__":
    main()

Sorting costs O(N log N + G log G). Each arrival enters and leaves the heap once, so the scan costs O((N + G) log N) overall and uses O(N) additional memory.

Submission

The service was an HTTP coding judge rather than a raw TCP protocol. Its page submitted source code to POST /run as JSON:

 json read-only • copy allowed Copy
{"code": "<solver source>", "language": "python"}

Submitting the solver from solve.py with the task-local submit.py script passed all hidden tests, and the response marked the challenge complete. The endpoint behavior and problem statement were also preserved in index.html; the acceptance record is documented in notes.md. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍