Problem Detail: Suppose we are given a list of $n$ points, whose $x$ and $y$ coordinates are all non-negative. Suppose also that there are no duplicate points. We can only go from point $(x_i, y_i)$ to point $(x_j, y_j)$ if $x_i le x_j$ and $y_i le y_j$. The question is: given these $n$ points, what is the maximum number of points that we can reach if we are allowed to draw two paths that connect points using the above rule? Paths must start from the origin and may contain repeated points. $(0, 0)$ is of course not included in the points reached. An example: given $(2, 0), (2, 1), (1, 2), (0, 3), (1, 3), (2, 3), (3, 3), (2, 4), (1, 5), (1, 6)$, the answer is $8$ since we can take $(0, 0) rightarrow (2, 0) rightarrow (2, 1) rightarrow (2, 3) rightarrow (2, 4)$ and $(0, 0) rightarrow (1, 2) rightarrow (1, 3) rightarrow (1, 5) rightarrow (1, 6)$. If we are allowed to draw only one path, I can easily solve the question by dynamic programming that runs in $O(n^2)$. I first sort the points by decreasing $x_i+y_i$. Let $D[i]$ be the maximum number of coins that one can pick up from coins $1$ to $i$ in the sorted list. Then $D[1] = 1$ and $D[i] = maxlimits_{1le j < i, x_j le x_i, y_j le y_i} D[j] + 1$. The answer then is just $maxlimits_{1le i le n} D[i] + 1$. But I cannot come up with a recurrence relation for two paths. If anyone has any idea about such a recurrence relation, I would be happy to hear what they are.
Asked By : Aden Dong
Answered By : Herm
The problem, restated and generalized: given a finite set $S$ equipped with a partial order $le$, find chains $C_1, C_2 subseteq S$ maximizing $lvert C_1 cup C_2 rvert$. The question is about the case where $S subseteq mathbb R_+^2$ and $(x, y) le (z, w) Longleftrightarrow x le z wedge y le w$. Naively, one might try to find the single best chain in $S^2$, where best is measured by how many distinct values the components of the chain have. Unfortunately, one component can retrace the steps of the other, e.g., $$bigl((0,0),(0,0)bigr) < bigl((1,0),(0,0)bigr) < bigl((2,0),(0,0)bigr) < bigl((2,0),(1,0)bigr),$$ so this notion of best does not have optimal substructure. Instead, we look for chains in the set $T := {(x, y) mid (x, y) in S^2 wedge x nless y wedge y nless x}$. By requiring that the components be equal or incomparable, we prevent retracing but now need to argue that some best chain conforms to the new requirement. Lemma 1 (no retracing). Let $C subseteq T$ be a chain and define $C_1 := {x mid (x, y) in C}$ and $C_2 := {y mid (x, y) in C}$. For all $z in S$, we have $z in C_1 cap C_2$ if and only if $(z, z) in C$. Proof. The if direction is trivial. In the only if direction, for all $z in C_1 cap C_2$, there exist $x, y in S$ such that $(x, z), (z, y) in C$. Since $C$ is a chain, $(x, z) le (z, y) vee (z, y) le (x, z)$. Assume symmetrically that $(x, z) le (z, y)$, which implies that $x le z le y$. We know by the definition of $T$ that $x nless z wedge z nless y$, so $x = z = y$, and $(z, z) in C$. Lemma 2 (existence of restricted best chain). For all chains $C_1, C_2 subseteq S$, there exists a chain $C subseteq T$ such that $C_1 subseteq {x mid (x, y) in C} subseteq C_1 cup C_2$ and $C_2 subseteq {y mid (x, y) in C} subseteq C_1 cup C_2$. Proof (revised). We give an algorithm to construct $C$. For convenience, define sentinels $bot, top$ such that $bot < x < top$ for all $x in S$. Let $C_1′ := C_1 cup {top}$ and $C_2′ := C_2 cup {top}$.
- Initialize $C := varnothing$ and $x := bot$ and $y := bot$. An invariant is that $x nless y wedge y nless x$.
- Let $x’$ be the next element of $C_1$, that is, $x’ := inf {z mid z in C_1′ wedge x < z}$. Let $y’$ be the next element of $C_2$, that is, $y’ := inf {w mid w in C_2′ wedge y < w}$.
- If $x’ nless y’ wedge y’ nless x’$, set $(x, y) := (x’, y’)$ and go to step 9.
- If $y < x’ < y’$, set $(x, y) := (x’, x’)$ and go to step 9.
- If $y nless x’ < y’$, set $x := x’$ and go to step 9. Note that $x < x’ wedge x nless y$ implies that $x’ nless y$.
- If $x < y’ < x’$, set $(x, y) := (y’, y’)$ and go to step 9.
- If $x nless y’ < x’$, set $y := y’$ and go to step 9. Note that $y < y’ wedge y nless x$ implies that $y’ nless x$.
- This step is never reached, as the conditions for steps 3–7 are exhaustive.
- If $x ne top$ (equivalently, $y ne top$), set $C := C cup {(x, y)}$ and go to step 2.
Dynamic Program. For all $(x, y) in T$, compute $$ D[x, y] := supbiggl(Bigl{D[z, w] + [x ne z] + [y ne w] – [x = y] mathrel{Bigl|Bigr.} (z, w) in T wedge (z, w) < (x, y)Bigr} cup bigl{2 – [x = y]bigr}biggr), $$ where $[textit{condition}] = 1$ if $textit{condition}$ is true and $[textit{condition}] = 0$ if $textit{condition}$ is false. By Lemma 1, it follows that the bracket expressions correctly count the number of new elements. By Lemma 2, the optimal solution to the original problem is found.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2553 Ask a Question Download Related Notes/Documents
