Sort the two dimension vectors separately into ascending order, $a_1\le \cdots \le a_d$ and $b_1\le \cdots \le b_d$. Then return true exactly when $a_i<b_i$ for every $i$. Sorting costs $O(d\log d)$ and the coordinate comparisons cost $O(d)$.

Sufficiency follows by matching corresponding ranks and translating that rank matching back to the original axes. For necessity, suppose $a_k\ge b_k$ for some $k$. The $d-k+1$ dimensions $a_k,\dots ,a_d$ must all be assigned to strictly larger target dimensions. None of the first $k$ sorted target dimensions is large enough, leaving at most $d-k$ eligible slots. The pigeonhole principle gives a contradiction. This proves the sorted-coordinate criterion for box containment, including ties: equality fails the required strict fit.

Permit every vertex to start a path: initialize $L[v]=0$ for all $v$, then perform the same maximum-relaxation pass in topological sorting order. Equivalently, the recurrence isThe zero option starts a fresh, zero-edge path; the other options extend an optimal path ending at a predecessor. The largest final entry is therefore the longest path length in the graph, allowing a zero-edge path. This takes $O(|V|+|E|)$, which is $O(|V{|}^2)$ for the ordinary simple-graph representation.

If at least one edge is required, keep the same prefix values but return ${\max }_{(u,v)\in E}(L[u]+w(u,v))$ instead of ${\max }_{v}L[v]$. That variant correctly returns a negative optimum when all nonempty paths have negative weight, and reports no nonempty path if the edge set is empty. No all-pairs repetition is needed.

Find a topological sorting of the directed acyclic graph. Initialize $L[s]=0$ and $L[v]=-\infty$ for $v\ne s$. Process vertices in that order. At a reachable vertex $u$, update each outgoing edge by $L[v]\leftarrow \max \{L[v],L[u]+w(u,v)\}$, and retain a predecessor whenever an improvement is made.

Every path to a vertex ends at an earlier vertex in the topological sorting. Thus, when $v$ is processed, all possible final-edge candidates for $v$ have already been considered. Induction along the order proves that $L[v]$ is the longest path length from $s$, with $-\infty$ exactly for unreachable vertices. Signed weights cause no problem because the graph has no directed cycle. The running time is $O(|V|+|E|)$, and predecessor pointers recover a maximizing path.

Use the multiplicative score exactly as defined in the paper. Let $P_t(v)$ be the largest score of a matching length-$t$ route ending at $v$. Initialize $P_0(v_0)=1$ and mark all other entries unreachable. For each stage, clear the new layer and inspect matching edges from reachable entries:An empty candidate set is marked unreachable, rather than given score zero: a genuine route may have score zero. A Boolean reachability table or a sentinel $-1$ with a guard before multiplication distinguishes the cases. Store the maximizing predecessor edge at each reachable layer entry, retaining one on a tie.

Multiplication by a nonnegative edge factor preserves order, so replacing a prefix by a larger-scoring matching prefix cannot worsen its extension. Induction proves this maximum-product edge-labelled walk recurrence correct. Choose a reachable final entry of greatest score and follow its layer-indexed predecessors backwards to reconstruct the answer. If no final entry is reachable, report that no matching route exists, even though all numeric scores might otherwise look like zero.

The running time is $O(k(|V|+|E|))$, and rolling scores have space complexity $O(|V|)$, while retaining all reconstruction pointers gives space complexity $O(k|V|)$. For the vertex-simple interpretation, retain the visited set in each state as in part i, prohibit revisits and maximize the same products over those states. This exact exponential-state variant preserves both the zero-score distinction and predecessor reconstruction. If the starting vertex is unrestricted rather than inherited from part i, initialize $P_0(v)=1$ for every vertex. The calculation needs no independence assumption beyond the paper's definition of a product score; repeated physical edge-activation events would require a separate probabilistic model.

The printed formula for the edge label has mismatched variable names. The type-correct reading is $x_i=\sigma (v_{i-1},v_i)$. Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.

Let $R_t$ be the set of vertices reachable from the specified start after reading exactly the first $t$ labels. Initialize $R_0=\{v_0\}$ and updateAfter $k$ stages, answer yes exactly when $R_k\ne \varnothing$. A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on $t$. Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is $O(k(|V|+|E|))$ with $O(|V|)$ rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at $v_0$.

If “path” is instead required to mean vertex-simple, augment the state to $(S,v)$, where $S$ is the set of visited vertices. Start with $R_0(\{v_0\},v_0)$ and extend a matching edge to $w$ only when $w\notin S$, replacing $S$ by $S\cup \{w\}$. This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when $k\ge |V|$. A straightforward bound is $O(k{2}^{|V|}(|V|+|E|))$ running time with $O(2^{|V|}|V|)$ rolling-table storage. The exponential distinction is substantive: all labels equal and $k=|V|-1$ include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.

Let $M_i[t]$ use only the first $i$ available coins. Initialize $M_0[0]=0$, $M_0[t]=\infty$ for $t>0$, and useomitting the second term when $t<x_i$. The alternatives exclude the current coin or use it once; both refer to the previous row, so it cannot be used twice. Induction on $i$ proves correctness, and $M_n[v]$ is the required answer, including $\infty$ when no selection works.

The running time is $O(nv)$. A single amount array reduces auxiliary space to $O(v)$ if each coin updates amounts in descending order, $t=v,v-1,\dots ,x_i$. Then $M[t-x_i]$ still describes the previous row. Ascending updates would reuse the same coin and solve a different, unlimited-supply problem.

During the computation in part i, record an index $\mathrm{last}[t]$ attaining the minimum at every positive amount. Starting with $t=v$, print $x_{\mathrm{last}[t]}$ and replace $t$ by $t-x_{\mathrm{last}[t]}$, continuing until $t=0$.

Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to $v$ and their number is exactly $M[v]$, proving optimality. The total running time is $O(nv+M[v])$, including the output; $M[v]\le v$ because denomination $1$ is available. The predecessor array adds $O(v)$ to the space complexity. This is reconstruction from the dynamic programming certificate, not the largest-denomination greedy algorithm, which need not be optimal for arbitrary denominations.

For nonnegative integer amount $v$, let $M[t]$ be the minimum number of coins making amount $t$. Set $M[0]=0$ and compute, in increasing order of $t$,An empty candidate set has minimum $\infty$. Here denomination $1$ ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on $t$.

Return whether $M[v]\le k$. This solves the at-most-$k$ decision without needing a separate dimension for $k$. The table for the minimum coin change recurrence takes $O(nv)$ running time and $O(v)$ space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.

Let $C$ be the final A set produced by the algorithm. It contains the initial A set, and every vertex outside $C$ has at most half its neighbours in $C$: otherwise its final key would still be positive. Thus $C$ is closed under the activation rule.

Now consider any legal sequence, including sequences which change some A preferences back to B. We prove by induction that its current A set is always a subset of $C$. This is true initially. A switch to B preserves the inclusion. If a vertex outside $C$ were to switch to A, its A neighbours would all lie in $C$, so their number could not exceed half its degree. Such a switch is forbidden. A switch inside $C$ also preserves the inclusion.

Consequently every attainable final A set has size at most $|C|$. The algorithm supplies a legal sequence attaining $C$ itself, so its sequence is optimal. This closure dominance for asynchronous threshold switching proves more than a local-greedy claim: temporary losses of A vertices cannot unlock an additional vertex outside the activation closure.

Only arrange switches towards A. For every vertex $u$, compute its degree $\mathrm{deg}(u)$ and the current number $c(u)$ of neighbours preferring A. Put the B vertices in a max-heap with key $q(u)=2c(u)-\mathrm{deg}(u)$. Maintain each vertex's current heap array index during exchanges.

While the queue is nonempty and its maximum key is positive, extract that vertex $u$, show it its neighbours' preferences, append $u$ to the answer sequence, and set its preference to A. For every neighbour $v$ still preferring B, increase $c(v)$ by one and use increaseKey to increase its heap key by two. Stop when every remaining key is nonpositive.

A positive key means precisely a strict majority of A neighbours, so every listed move is legal. Degrees never change; A neighbours never revert in this chosen sequence. An isolated B vertex has key zero and cannot be converted. Initialization costs $O(|V|+|E|)$, there are at most $|V|$ extractions, and each edge causes at most two neighbour inspections and at most a constant number of key updates. The required bound is therefore $O((|V|+|E|)\log (|V|+1))$. A simple work queue of newly eligible vertices can even implement the same monotone threshold activation in $O(|V|+|E|)$ time, since a vertex needs to be enqueued only once.

Leaves already obey the heap order. Process indices $\lfloor n/2\rfloor ,\lfloor n/2\rfloor -1,\dots ,1$, calling the preceding repair at each. When an index is processed, its descendants have already been processed, so the repair's precondition holds. The resulting array is a max-heap.

The bound obtained by charging $O(\log n)$ to every call is unnecessarily large. The number of nodes with height at least $h$ is at most $\lfloor n/2^h\rfloor$. ThereforeThe total repair work is thus $O(n)$, and the loop itself has a linear number of iterations, giving $\Theta (n)$ for this bottom-up heap construction. Most nodes are near the leaves and require little repair.

Assume the subtrees rooted at the children in a rooted tree of $i$ already obey the max-heap condition. Compare $A[i]$ with each present child and choose an index of the largest of these at most three keys. If that index is $i$, stop. Otherwise exchange the two keys, continue at the chosen child, and repeat. This is sift down, with the inequality reversed from a minimum-oriented binary heap.

The exchange repairs the old root position because its new key dominates both child roots; only the subtree receiving the displaced key can still be defective. This recursion invariant proves correctness. Each exchange descends one level and costs constant work, so the worst-case running time is $O(h)$ for subtree height $h$, hence $O(\log n)$. A small key at the root of a suitably ordered heap must descend to a leaf, so the logarithmic worst-case bound is attained.

Store a complete binary tree in a one-indexed array $A[\mathrm{1..}n]$, level by level. Index $i$ has parent in a rooted tree $\lfloor i/2\rfloor$ for $i>1$ and possible children in a rooted tree $2i$ and $2i+1$, present only when their indices are at most $n$. The max-heap condition is $A[\lfloor i/2\rfloor ]\ge A[i]$ for every $i>1$.

Following these inequalities from the root of a tree to any entry proves that $A[1]$ is a maximum. The heap order does not sort siblings or unrelated branches. The complete binary tree has height $\lfloor {\log }_{2}n\rfloor$, which bounds how far any single repair can travel. Store the current heap size separately from the array's capacity.

Restrict the unknown function to the $n$ possibilities $f^{(i)}(x)=1$ if $x_i=1$, and $2$ otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.

A correct adaptive deterministic algorithm must distinguish all $n$ possibilities. A binary decision tree of depth $q$ has at most $2^q$ leaves, so $2^q\ge n$. Therefore $q\ge \lceil {\log }_{2}n\rceil =\Omega (\log n)$. Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed $d$.

If $n=1$, return its sole index without a query. Otherwise first evaluate $f(t,t,\dots ,t)$ for $t=1,\dots ,d$ until two different outputs are found. Part i says these outputs are precisely $f_i(t)$, so two values $a,b$ with $f_i(a)\ne f_i(b)$ must exist. This uses at most $d$ calls to the function-evaluation oracle.

Maintain a candidate index set $S$, initially all indices. Split $S$ into two nearly equal pieces and choose one, $H$. Query the input that is $b$ on $H$ and $a$ everywhere else. Its output equals $f_i(b)$ exactly when $i\in H$, and otherwise equals $f_i(a)$. Retain the indicated half and repeat until one index remains.

The loop invariant is $i\in S$, and the witness outputs keep each test unambiguous. There are at most $\lceil {\log }_{2}n\rceil$ splitting queries. The total is at most $d+\lceil {\log }_{2}n\rceil$ evaluations, which is $O(d\log n)$ for $n\ge 2$, and in fact a stronger additive bound. Only oracle calls are being counted; explicitly constructing each query vector can require $O(n)$ ordinary work. This is identification of a unique essential variable.

If coordinate $j$ is not an essential variable of a function, changing that coordinate alone never changes the output, for any values of the other coordinates. Take two inputs with the same $i$-th coordinate. Change their other coordinates one at a time to transform the first input into the second. Every such change is inessential, so all intermediate outputs are equal.

Define $f_i(t)=f(1,\dots ,1,t,1,\dots ,1)$, with $t$ in position $i$. The preceding argument gives $f(x_1,\dots ,x_n)=f_i(x_i)$. Since $i$ is essential, $f_i$ is nonconstant. The conclusion depends on the full “for every context” negation of essentiality, not merely on testing a coordinate at one selected input.

Represent the removed half as the first $m=500$ cards in a uniformly random ordering. Every unordered half is then equally likely. Let $X_1,\dots ,X_{500}$ be their values. Each has mean zero and variance one, and every distinct pair has covariance $-1/999$ by the same ordered-pair argument as in (ii).

The general covariance expansion from (b), applied without imposing independence, givesThis is the finite population correction for a half-sample; treating the draws as independent would give the wrong variance.

Finally $\{Z\ge 50\}\subseteq \{|Z|\ge 50\}$, so Chebyshev's inequality yieldsThe cards returned before this sampling step restore the original population; no conditioning on the earlier two observed values is imposed.

Every particular card is second with probabilityHence $X$ and $Y$ have the same distribution, with means zero and variances one. They are not independent, since a card cannot be drawn twice.

Every ordered pair of distinct cards has probability $1/(1000\cdot 999)$. ThereforeThis negative covariance is the effect of sampling without replacement, not a contradiction of their identical marginals.

Write the card values as $a_1,\dots ,a_{1000}$. Uniform selection givesThus $\mathbb{E}[X]=0$ and $\mathrm{Var}(X)=1$, by the variance identity $\mathrm{Var}(X)=\mathbb{E}[X^2]-\mathbb{E}[X{]}^2$.

**Chebyshev's inequality: if $X$ has finite mean $\mu$ and variance ${\sigma }^2$, then for $a>0$,Apply Markov's inequality to the nonnegative random variable $Y=(X-\mu {)}^2$ with threshold $a^2$. Since $\mathbb{E}[Y]={\sigma }^2$ and $\{|X-\mu |\ge a\}=\{Y\ge a^2\}$, the desired statement follows immediately.