Dynamic Programming Questions

import math
import random
def expected_turns(N, jump, max_iters=200000, tol=1e-9, omega=1.2):
    # N: number of squares, indexed 0..N-1. start=0, goal=N-1.
    # jump: dict mapping index -> new index (after applying forward/backward square), optional
    goal = N-1
    def next_state(i, roll):
        s = i + roll
        if s >= N: return goal
        return jump.get(s, s)
    # Build static neighbors and probabilities
    neighbors = [[] for _ in range(N)]
    for i in range(N):
        if i == goal: continue
        freq = {}
        for r in range(1,7):
            ns = next_state(i, r)
            freq[ns] = freq.get(ns, 0) + 1/6.0
        neighbors[i] = list(freq.items())  # (next_state, prob)
    # Detect states that cannot reach goal via BFS on directed edges
    rev = [[] for _ in range(N)]
    for i in range(N):
        for ns, p in neighbors[i]:
            rev[ns].append(i)
    reachable = [False]*N
    stack = [goal]; reachable[goal]=True
    while stack:
        u = stack.pop()
        for v in rev[u]:
            if not reachable[v]:
                reachable[v]=True; stack.append(v)
    if not reachable[0]:
        return math.inf  # start cannot reach goal
    # Initialize E
    E = [0.0 if i==goal else 10.0 for i in range(N)]
    # Gauss-Seidel with SOR
    for it in range(max_iters):
        max_diff = 0.0
        for i in range(N):
            if i==goal: continue
            # if state can't reach goal, expectation is infinite; skip (we handled start)
            if not reachable[i]:
                E[i] = math.inf
                continue
            rhs = 1.0
            for ns, p in neighbors[i]:
                rhs += p * E[ns]
            # equation: E[i] = rhs
            new_val = rhs
            # SOR relaxation
            updated = (1-omega)*E[i] + omega*new_val
            diff = abs(updated - E[i])
            E[i] = updated
            if diff > max_diff: max_diff = diff
        if max_diff < tol:
            break
    return E[0]

# assume 0-based, n items, dp initialized large, opt init
for i in range(n):
    dp[i][i] = 0
    opt[i][i] = i

for length in range(1, n):
    for i in range(0, n-length):
        j = i + length
        # search limited by monotone opt bounds
        left = opt[i][j-1]
        right = opt[i+1][j] if i+1<=j else j-1
        best = INF
        best_k = left
        for k in range(left, right+1):
            val = dp[i][k] + dp[k+1][j] + w(i,j)
            if val < best:
                best = val
                best_k = k
        dp[i][j] = best
        opt[i][j] = best_k

from bisect import bisect_left

def lis_with_reconstruction(a):
    n = len(a)
    tails_vals = []
    tails_idx = []
    prev = [-1]*n

    for i, x in enumerate(a):
        pos = bisect_left(tails_vals, x)  # first >= x
        if pos == len(tails_vals):
            tails_vals.append(x)
            tails_idx.append(i)
        else:
            tails_vals[pos] = x
            tails_idx[pos] = i
        if pos > 0:
            prev[i] = tails_idx[pos-1]

    length = len(tails_vals)
    # reconstruct one LIS
    lis = []
    cur = tails_idx[-1] if tails_idx else -1
    while cur != -1:
        lis.append(a[cur])
        cur = prev[cur]
    lis.reverse()
    return length, lis

import java.util.*;
class LongestPathDAG {
    static class Edge { int to; int w; Edge(int t,int w){to=t;this.w=w;} }
    // Returns pair: distances[] and predecessors[] (use -1 for unreachable)
    static Map<String,Object> longestFrom(int n, List<List<Edge>> g, int src) {
        int[] indeg = new int[n];
        for(int u=0;u<n;u++) for(Edge e: g.get(u)) indeg[e.to]++;
        // Kahn's topo
        Queue<Integer> q = new ArrayDeque<>();
        for(int i=0;i<n;i++) if(indeg[i]==0) q.add(i);
        List<Integer> topo = new ArrayList<>();
        while(!q.isEmpty()){
            int u=q.poll(); topo.add(u);
            for(Edge e: g.get(u)) if(--indeg[e.to]==0) q.add(e.to);
        }
        double[] dist = new double[n];
        int[] pred = new int[n];
        Arrays.fill(dist, Double.NEGATIVE_INFINITY);
        Arrays.fill(pred, -1);
        dist[src]=0;
        // Relax edges in topo order
        for(int u: topo){
            if(dist[u]==Double.NEGATIVE_INFINITY) continue;
            for(Edge e: g.get(u)){
                if(dist[u] + e.w > dist[e.to]){
                    dist[e.to] = dist[u] + e.w;
                    pred[e.to] = u;
                }
            }
        }
        Map<String,Object> res = new HashMap<>();
        res.put("dist", dist);
        res.put("pred", pred);
        return res;
    }
    // reconstruct path to target
    static List<Integer> reconstruct(int[] pred, int target){
        List<Integer> path = new ArrayList<>();
        for(int cur=target; cur!=-1; cur=pred[cur]) path.add(cur);
        Collections.reverse(path);
        return path;
    }
}

def max_subarray_bounded(A, L, R):
    """
    A: list[int], 1-index lengths L,R with 1 <= L <= R <= n
    Returns max subarray sum with length in [L, R].
    """
    n = len(A)
    if n == 0 or L > n:
        return None  # or -inf depending on spec

    # prefix sums
    S = [0] * (n + 1)
    for i in range(1, n + 1):
        S[i] = S[i - 1] + A[i - 1]

    from collections import deque
    dq = deque()  # will store indices j with increasing S[j]
    ans = float("-inf")

    for i in range(1, n + 1):
        # Add index j = i - L as it becomes eligible (window upper bound)
        j_add = i - L
        if j_add >= 0:
            # maintain increasing S[j] in deque
            while dq and S[dq[-1]] >= S[j_add]:
                dq.pop()
            dq.append(j_add)

        # Remove indices j < i - R (out of lower bound)
        j_min = i - R
        while dq and dq[0] < j_min:
            dq.popleft()

        # If deque not empty, front is index of minimal S[j] in window
        if dq:
            ans = max(ans, S[i] - S[dq[0]])

    return ans