Hard Drill

Choose the balloon k that bursts last in (l, r). At that point its neighbours are l-1 and r+1, so dp[l][r] = max over k of dp[l][k-1] + dp[k+1][r] + a[l-1]·a[k]·a[r+1].

Edge (i, j) belongs to exactly one triangle (i, k, j). dp[i][j] = min over k of dp[i][k] + dp[k][j] + v[i]v[k]v[j].

Add 0 and n to the cuts and sort them. Run the DP over cut indices. The cost of a segment is cuts[j] - cuts[i], whichever cut happens first.

dp[l][r] = dp[l+1][r] + 1, or for any k with s[k] == s[l], merge s[l]'s stroke into s[k]'s: dp[l+1][k-1] + dp[k][r].

Same structure as Strange Printer: delete s[l] alone, or save it for the same deletion as a later equal character k.

dp[l][r] = min(1 + dp[l+1][r], 1 + dp[l+2][r] if c[l] == c[l+1], dp[l+1][k-1] + dp[k+1][r] for c[k] == c[l]). Gem l is removed together with gem k, wrapped around the middle.

If (n-1) % (K-1) ≠ 0 the answer is -1. dp[l][r] is the cost of merging the range down as far as possible. Split at m in steps of K-1, and add the range sum when (r-l) % (K-1) == 0.

Two dimensions aren't enough. Add a third: dp[l][r][k], where k boxes equal to box[l] are attached on the left. Either remove them now, or join them with a later equal box.

Multi-source BFS over (node, visited mask), starting from every node with mask = 1<<node.

dp[mask] means nums2 elements in mask are used. The next nums1 index is popcount(mask).

Iterate over people; dp[mask | skills[p]] = min(dp[mask] + 1). Store a parent pointer instead of copying lists.

Precompute pairwise overlaps. Then it's TSP: dp[mask][last] = max total overlap. Reconstruct the string from parent pointers.

Greedy topological order is wrong. dp[mask] = minimum semesters. avail = courses whose prerequisites are all in mask; try every submask of avail with size ≤ k (or all of avail if it fits).

Row-by-row mask DP. cur must avoid broken seats and have no adjacent bits; it's compatible with prev if (cur<<1 & prev) and (cur>>1 & prev) are both 0.

Each slot holds 2 numbers, so use 2·numSlots bits. The number being placed is popcount(mask).

You need some b with a & b = 0, so b ⊆ ~a. SOS DP: best[mask] = any element that is a submask of mask.

Shorter lengths contribute d^len for free. Then walk n's digits while tight.

Per position: split into high / cur / low and count how often this digit is 1. This is the contribution form of a digit DP.

State (pos, used-digit mask, tight, started). Zeros before the number starts don't go into the mask.

Count the complement: n minus the numbers ≤ n with all distinct digits.

dp(pos, digit sum, tight), with the sum capped at max_sum. The answer is f(num2) - f(num1) + [num1 itself is valid].

State (pos, non-zero digits so far ≤ 3, tight).

Store each edge in both directions: cost 0 along the original direction, 1 against it. Count the cost for root 0, then moving the root across an edge flips that edge's contribution.

down[v] = a[v] + Σ max(0, down[child]). Then full[child] = down[child] + max(0, full[v] - max(0, down[child])).

res[child] = res[v] + total - 2·sub[child], where sub is the subtree weight sum.

Three states per node: no camera and uncovered, covered without a camera, has a camera. Equivalently, greedily put cameras on the parents of leaves.

ans[child] = ans[v] - size[child] + (n - size[child]). Moving the root one step brings size[child] nodes closer and pushes the rest further away.

Same as Treeland: forward edge costs 0, reverse costs 1, then reroot.

Count the correct guesses for root 0. Moving the root from u to v changes only the guesses (u, v) and (v, u).

At each node keep the two longest child chains whose character differs from the node's. The answer is 1 + best1 + best2.

The number of components must divide the total. For each divisor, DFS returns the subtree sum, cuts when the sum equals the target and fails when it goes over.

The cost is a path sum minus one endpoint. For each node keep two values: the best chain down that includes its leaf, and the best that excludes it. Combine at each node.

Tree knapsack: dp[v][k][coupon used?]. Merging children in order of size keeps the total at O(n²).

DFS with memoisation. Strictly increasing moves can't cycle, so no visited set is needed.

Longest path with node weights, computed in topological order.

Kahn's algorithm with dp[node][colour] = maximum count of that colour on any path ending at node. Return -1 if there's a cycle.

dp[j][holding]. If k ≥ n/2 the limit doesn't bind, so treat it as unlimited.

States are (absences 0–1, trailing lates 0–2): 6 states, O(n). For huge n, use matrix exponentiation.

dp[i][k]: either delete s[i], or keep s[i] as the start of a run and scan ahead, deleting the characters that differ, while tracking the run length.

dp[t][j] = probability that j people are on the escalator after t seconds.

Spread probability over k steps; each move gets 1/8.

Divide by 25. For n ≥ about 4800 the answer is 1 to within the allowed error.

dp[x] = (sum of dp[x-maxPts .. x-1] restricted to values < k) / maxPts, kept as a sliding window sum. The answer is Σ dp[k..n].

Non-decreasing LIS: bisect_right on the tails array; the answer at i is the insert position + 1.

dp[i] = nums[i] + max(dp[i-k .. i-1]), taken from a monotonic deque.

Sort by end time. dp[i] = max(dp[i-1], profit[i] + dp[last job ending ≤ start[i]]), found by binary search.

dp[i][k], with the next index found by binary search.

Like Jump Game VI, but take max(0, window max).

Sort by width ascending and height descending, so equal widths can't chain, then run strict LIS on the heights.

Negative values rule out a sliding window. Keep prefix indices in a deque with increasing values; pop from the front while P[i] - P[front] ≥ k.

dp[n][k] = dp[n][k-1] + dp[n-1][k] - dp[n-1][k-n] (a prefix-sum telescope).

dp[i] = min over j of dp[j] + b[j]·a[i]. The slopes b decrease and the queries a increase, so a monotone convex hull trick deque works.

The optimal split point is monotone, so use divide-and-conquer DP. Compute cost(l, r) with Mo-style moving pointers.

Place the shortest stick last in reasoning: it's visible only if it comes first. dp[n][k] = dp[n-1][k-1] + (n-1)·dp[n-1][k].

ways(T) = C(|L|+|R|, |L|) · ways(L) · ways(R). Subtract 1 for the original order.

dp[i][j] = dp[i-1][j-1]·(n-j+1) + dp[i-1][j]·max(j-k, 0).

dp[i][j] = number of ways where the last element has relative rank j among the first i+1. Prefix sums over j.

The number of topological orders of a rooted tree is n! / ∏ size(v).

dp[i][j] = dp[i-1][j] + (s[i] == t[j]) · dp[i-1][j-1]. Iterate j backwards to use 1D.

Expand around each centre and update cut[r+1] = min(cut[r+1], cut[l] + 1). O(n²) with no palindrome table.

total' = 2·total - (count just before the previous occurrence of this character).

For 'x*': use it zero times (dp[i][j-2]), or once more if x matches (dp[i-1][j]).

Per character c: look at the first and last occurrence of c inside [l, r]. If there's none, one, or more than one, the recurrence differs. Don't double-count.

dp[i] = max over x in 1..3 of (sum of the x stones taken - dp[i+x]).

dp[i][M] = suffix[i] - min over x in 1..2M of dp[i+x][max(M, x)].

State (mouse, cat, turn). Seed the known results (mouse at the hole, cat catches mouse) and propagate backwards: a state is a loss once all its moves lead to wins for the opponent. Whatever is left is a draw.

dp[row][c1][c2].

m ≤ 5, so there are at most 48 valid columns. Build the compatibility matrix and run n steps.

Going there and back equals two forward paths. dp[t][r1][r2], with c = t - r.

Broken profile: process one cell at a time with a base-3 code of the last n cells, plus the number of introverts and extroverts left.

Monotonic stack gives left[i] and right[i]. The contribution is a[i] · left · right.

Each occurrence adds (i - last[c]) · (n - i).

Each occurrence adds (i - prev) · (next - i).

f(n) = f(n-1) + f(n-M), with an M×M companion matrix.

Replace each query vertex with its parent, then check they all lie on the root path to the deepest one, using tin and tout.

A binary lifting table, about 17 levels.

Keep a count of each weight 1..26 from the root to every node. Path count = c[u] + c[v] - 2·c[lca]. Answer = path length - largest count.

Offline DFS with a difference array indexed by depth: add on entry, undo on exit.

A segment tree over the Euler tour storing a 60-bit colour mask, with lazy assignment. Answer with popcount.

Value signs alternate by depth parity. Use a BIT range update over the subtree, with the sign set by depth.

Bucket nodes by depth in tin order and binary search the subtree range. A palindrome is possible if the XOR of letter parities has at most 1 bit set.

Small-to-large on maps of colour counts, carrying (best frequency, sum of colours with it).

Rank = depth in the centroid tree. It's always possible because the depth is at most log n ≤ 26.

Fill a subtree = range assign on the Euler tour. Empty the path to the root = HLD path assign.

For each centroid ancestor c of the painted node, best[c] = min(best[c], dist). A query takes the min of best[c] + dist(v, c).

Peel leaves layer by layer; the last 1 or 2 nodes left are the centres.

n ≤ 15. Enumerate subsets, check each is connected, and take its diameter from Floyd-Warshall distances.

Repeatedly remove leaves without coins, then strip 2 more layers of leaves. The answer is 2 · (edges remaining).

Count the dashes to get the depth, then use a stack trimmed to that depth.

Post-order returns (isBST, min, max, sum).

Two DFS passes: left-first and right-first, each carrying the maximum height reached so far before entering a node. The answer for a node combines what lies outside its subtree.

XORing along a path toggles only its two endpoints, so you can toggle any even-size set of nodes. Greedy or DP on parity; the tree shape doesn't matter.

Precompute subtree XORs and tin/tout. Try all O(n²) pairs of edges, using the ancestor test to work out the three components.

A trie with counts supporting insert, delete and maximum XOR.

Greedy trie walk from the top bit.

Offline: sort the queries by m and insert numbers ≤ m as you go.

Offline DFS: insert a node on entry, answer the queries at that node, delete it on exit.

Bellman-Ford for k+1 rounds, copying the distance array each round.

BFS over (r, c, eliminations left). If k ≥ m + n - 2, return the Manhattan distance.

0-1 BFS: following a cell's arrow costs 0, any other direction costs 1.

Dijkstra that also counts ways: on a tie, ways[v] += ways[u]; on an improvement, reset.

0-1 BFS where a cell's weight is whether it's an obstacle.

BFS keeping the first two distinct arrival distances per node, then simulate the red/green traffic signals for that number of edges.

Dijkstra on the original nodes. Edge (u, v, cnt) adds min(cnt, max(0, M - d[u]) + max(0, M - d[v])).

If both neighbours of the start are blocked, return -1. Otherwise you can wait by stepping back and forth, so the arrival time is raised to the cell's time, adjusted for parity.

sum - max + min equals using one edge twice and another edge zero times. Run Dijkstra over (v, doubled used?, zeroed used?), with 4 layers.

Multi-source BFS from the thieves gives a safety grid. Then find the max-min path with a max-heap Dijkstra or binary search + BFS.

Three Dijkstras: from src1, from src2, and from dest on the reversed graph. Answer = min over meeting node x of the three distances summed.

Within each SCC, take the minimum cost and count how many nodes have it; multiply the counts.

Tarjan bridges.

Possible if and only if there are no bridges. Orient tree edges downward and back edges upward.

Each door is controlled by exactly 2 switches, which gives an XOR constraint. Use a parity DSU, or 2-colouring.

The answer is always 0, 1 or 2. Check whether it's already disconnected, then try removing each cell.

Sort the edges; each union adds size[a] · size[b] pairs. Answer the sorted queries as you sweep.

For each infected node, BFS while avoiding the other infected nodes. Count the clean nodes reached only from this one.

Add type-3 edges to both DSUs first, then type 1 and type 2.

Offline: sort the queries by limit and add edges with weight < limit.

Activate nodes in increasing value, uniting each with neighbours of value ≤ its own. For each value, a component with c such nodes adds C(c, 2) + c paths.

Reverse time. Remove every hit, union the remaining bricks (with a virtual roof node), then add the hits back in reverse and measure how much the roof component grows.

Add edges from the minimum-a vertex to every vertex, then run Kruskal.

For each edge, run Kruskal without it (critical if the weight rises or the graph disconnects) and with it forced in (pseudo-critical if the weight equals the base).

Two independent topological sorts, one for rows and one for columns.

Two-level topological sort: groups first, then items within each group.

Hierholzer with min-heap adjacency lists.

De Bruijn sequence: an Euler circuit over the (n-1)-digit prefixes.

Find the start (out - in = 1), then Hierholzer.

Walk from each unvisited node, stamping times. Revisiting a node from the current walk gives the cycle length as the time difference.

Nodes on a cycle get the cycle length. The rest get 1 + ans[next], computed in topological peel order.

The answer is max(the largest cycle of length ≥ 3, the sum over all 2-cycles of 2 + the longest chains into both ends).

k goes up to 1e10. Binary lifting storing (node after 2^j steps, sum of ids along the way).

BFS over routes rather than stops. Map each stop to its routes and mark each route used once.

BFS over (r, c, key mask).

BFS over (box position, player side). For each push, run an inner BFS to check the player can reach the pushing cell.

If any component isn't bipartite, return -1. Otherwise sum, over components, the maximum BFS depth from any start node in it.

Union cells in order of height until the start and end are connected; equivalently, Dijkstra with max.