The cost for Power Ups has changed since version 0.7, so this post is no longer applicable.

What is the optimal order for buying all Power Ups?

Given a directed acyclic graph $G = (V, E)$ and a node weight function $w: V \to \mathbb{N}$, find a topological ordering $v_{i_1}, \dots, v_{i_n}$ to minimize $\sum\limits_{i=1}^n i w(v_{a_i}).$

We start with Linear Arrangement, an NP-hard problem, which will be defined below and used for reduction.

One can easily show that Linear Arrangement is equivalent to minimizing $\sum_{(u, v) \in E} \max(f(u), f(v))$, as $|f(u) - f(v)| = 2 \max(f(u), f(v)) - f(u) - f(v)$. We now reduce the Linear Arrangement instance to a Weighted Topological Sort instance.

Let $OPT$ be the optimal $\sum_{(u, v) \in E} \max(f(u), f(v))$ in the Linear Arrangement instance, and let $f^*$ be the corresponding mapping. Similarly, let $OPT'$ be the minimum total cost in the constructed instance, and let $v'^*$ be the corresponding solution.

We first show that $OPT' < K \cdot OPT + K$. We determine the order of $V'_i$ as $\left[V'_{f^{*-1}(1)}, V'_{f^{*-1}(2)}, \dots, V'_{f^{*-1}(n)} \right]$ and then insert all edges $e \in E$ as early as possible. Since at most $|E|$ edges are inserted, the completion time for an edge $e$ is bounded by $c(e) < K \max(f^*(u), f^*(v)) + |E|$, which gives a total cost of

Now, we construct an optimal solution $f$ from $v'^*$. We consider the subsequence $\left\{v_{a_i}^{(K)} \right\}_i$ in $v'^*$ and define $f\left(v_{a_i} \right) = i$. The completion time $c(e)$ for an edge $e = (u, v)$ has a lower bound of $c_e > K \max(f(u), f(v))$, which in turn provides an upper bound on $\sum_e \max(f(u), f(v))$:

Note that $f$ maps nodes to integers, so the first inequality must be an equality, which means $f$ is an optimal mapping for the Linear Arrangement instance.

Given a directed acyclic graph $G = (V, E)$ and a node weight function $w: V \to \mathbb{N}$, find a topological ordering $v_{i_1}, \dots, v_{i_n}$ to minimize $\sum\limits_{i=1}^n i w(v_{a_i}).$ The graph $G$ contains only $k$ chains:

Let $v^*$ be the optimal ordering. Let a segment be an interval of nodes from the same chain. Since $v^*$ is optimal, swapping adjacent segments that come from different chains won’t improve the objective. This can be formulated as: let $v_{i_1, \{l_1, \dots, r_1\}}$ and $v_{i_2, \{l_2, \dots, r_2\}}$ be adjacent segments where $i_1 \neq i_2$, then:

After simplification, it becomes:

We define the weight of a segment $w(v_{i, \{l, \dots, r\}}) := \frac{1}{r - l + 1} \sum\limits_{j=l}^r w(v_{i, j})$, so the inequality above simply means that $w(v_{i_1, \{l_1, \dots, r_1\}}) \geq w(v_{i_2, \{l_2, \dots, r_2\}})$, and all maximal segments in $v^*$ are sorted in descending order.

Now, let us consider the chain $V_i$. We start with $n_i$ chains, each containing only one node. Now we’re trying to merge adjacent nodes: If there exist two adjacent segments $v_{i, \{a, \dots, b\}}$ and $v_{i, \{b + 1, \dots, c\}}$ such that $w(v_{i, \{a, \dots, b\}}) <$ $w(v_{i, \{b + 1, \dots, c\}})$, we can merge them into one segment $v_{i, \{a, \dots, c\}}$. The reason is: If there is another segment $v_{i', \{l', \dots, r'\}}$, one of the following must be true:

which contradicts our previous observation. The process of merging can be summarized in the following pseudocode:

def merge_segments(chain):
   segments = []
   for v in chain:
       cur_seg = [v]
       while segments and w(segments[-1]) < w(cur_seg):
           cur_seg = segments.pop() + cur_seg
       segments.append(cur_seg)
   return segments

After merging segments, all segments in chain $i$ are sorted in descending order of $w$. This naturally leads to a greedy algorithm: The best candidate in each chain will be the current first segment, so we don’t have any dependency issues!

def optimal_order(chains):
   segments = [seg for chain in chains for seg in merge_segments(chain)]
   segments = sorted(segment, key=w)
   return [v for seg in segments for v in seg]

The code above is inefficient in its representation of segments and can be easily optimized to $O(n \log n)$, where $n = |V|$.

Let $S$ be a multiset containing $3n$ positive integers. Can we partition $S$ into $n$ multisets, each containing 3 elements with a sum $s = \frac{1}{n} \sum\limits_{e \in S} e$?

Given an instance of the 3-Partition problem (where we assume every element in $S$ is strictly greater than 1), we construct the following problem:

From the Rearrangement Inequality, $3n$ is a lower bound of the objective, and it is only attained if $c(v_{i, 1}) \bmod s \in \{1, 2, 3\}$ and $c(v_{i, S_i}) \bmod s \in \{0, s - 1, s - 2\}$ for all chains $i$. In this case, the optimal ordering can be split into $n$ intervals evenly, each consisting of 3 complete chains, which means the 3-Partition instance is satisfiable.

Given a DAG, the task is to sort all vertices topologically, such that vertex 1 has the smallest index. Break ties by minimizing the index of vertex 2, 3, and so on, until $n$.