Nether Portal: Deadline Feasibility¶
Codex (GPT-6) provides the independent backward decision algorithm in alternative-deadline.cpp. The main solution retains the setter's predecessor-cycle acceleration. Both pass all tests. This version has an explicit polynomial worst-case bound but requires multiple decisions.
Shared Model¶
Each portal state is its ready time after opening, with virtual start and target states. A nonnegative-step world gives \(x_v=\max(t_v,x_u+c_{uv})\) ; a negative-step world resets directly to \(t_v\) . There are \(V=N+2\) vertices and \(E\le52V\) edges. Handle unreachable targets and negative-time target worlds first; see the main solution for the full reduction.
Decision and Binary Search¶
For a deadline \(X\) , propagate backward the latest ready time \(L_u\) that can still reach the target in time. Initialize the target to \(X\) . An affine edge gives \(L_u=L_v-c_{uv}\) , usable only when it is at least \(t_u\) . Reaching the start with \(L_0\ge0\) proves feasibility.
A backward-reached reset edge with a forward-reachable source also proves feasibility: its source can arrive arbitrarily late and still take enough negative-time round trips. Improvements persisting for \(V\) rounds imply a positive-gain backward cycle. Repeating it permits arbitrarily late entry; forward reachability and waiting then connect the start to it. Without a beneficial cycle, a witness can be simplified to at most \(V-1\) edges, proving the round criterion.
Binary search \([-20000,U]\) , where \(U\) comes from an actual traversal along any reachable world route. Time is \(O(VE\log(U+20001))\) and space is \(O(V+E)\) . This reverses the direction and uses feasibility rather than direct minimization, providing an independent comparison. Its worst-case bound is simpler, at the cost of repeated decisions. Both implementations pass the formal time limit; see test details.