8
$\begingroup$

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] = \max\limits_{1\le j < i, x_j \le x_i, y_j \le y_i} D[j] + 1$. The answer then is just $\max\limits_{1\le 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.

$\endgroup$
  • $\begingroup$ I would sort the points lexicographically, but I guess it does not matter. You should definitely anchor in $D[0]$; the best path may not use the first coin. Also, the way you choose the result suggests that the best path has to use the last point. Furthermore, due to the nasty structure, this problem seems to be ill-suited for DP. Finding longest paths in the DAG implied by the points would make much more sense. $\endgroup$ – Raphael Jun 30 '12 at 17:46
  • $\begingroup$ Well for one path the last point doesn't need to be included. If for some point $i$ there is no point to the right and above of it then $D[i]$ would simply be $1$. I guess I should have made that more clear though. $\endgroup$ – Aden Dong Jul 1 '12 at 2:39
  • $\begingroup$ Could you not simply run the algorithm twice, but in the second pass remove all points touched in the first path? Or is a single recurrence relation required? $\endgroup$ – edA-qa mort-ora-y Jul 1 '12 at 13:41
4
$\begingroup$

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\}$.

  1. Initialize $C := \varnothing$ and $x := \bot$ and $y := \bot$. An invariant is that $x \nless y \wedge y \nless x$.

  2. 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\}$.

  3. If $x' \nless y' \wedge y' \nless x'$, set $(x, y) := (x', y')$ and go to step 9.

  4. If $y < x' < y'$, set $(x, y) := (x', x')$ and go to step 9.

  5. 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$.

  6. If $x < y' < x'$, set $(x, y) := (y', y')$ and go to step 9.

  7. 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$.

  8. This step is never reached, as the conditions for steps 3–7 are exhaustive.

  9. 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] := \sup\biggl(\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.

$\endgroup$
  • $\begingroup$ Nice. I have not checked every detail, though. Welcome to cs.SE! $\endgroup$ – Raphael Jun 30 '12 at 19:12
0
$\begingroup$

Let $P = p_1\dots p_n$ to sorted list of points.


Following your recurrence for one path, the first thing to note is that you have to keep track of which points have been visited by the paths; otherwise you can not count correctly. The second thing is that you have now four possibilities for every point: neither path may use it, one of them or both. So, we have to find maximising combinations for all three cases.

Formally, let $d : [0\dots n] \to (2^{[n]} \times 2^{[n]})^3$ with $d(i)$ the pair of (sets of) visited nodes of the two paths that maximise the number of visited points from the input set up to the $i$th one, with the first component the maximising pair of paths for which the first one uses $p_i$, the second component similar for the second path and the third component with both paths using $p_i$. $d$ is given by the recurrence

$\quad \displaystyle \begin{align} d(0) &= ((\emptyset, \emptyset),(\emptyset, \emptyset),(\emptyset, \emptyset)) \\ d(i) &= (\ \arg\max_{(L,R) \in (\mathcal{L}' \times \mathcal{R})_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max_{(L,R) \in (\mathcal{L} \times \mathcal{R}')_i} |L \cup R|, \\ &\phantom{= (\ } \arg\max_{(L,R) \in (\mathcal{L}' \times \mathcal{R}')_i} |L \cup R| \ ) \\ \end{align}$

with

$\quad \displaystyle (\mathcal{L}' \times \mathcal{R})_i = \left\{ (L \cup \{i\}, R) \mid (L,R) \in \bigcup_{j=0}^{i-1} d(j), x_i \geq \max_{j \in L} x_j, y_i \geq \max_{j \in L} y_j \right\}$,

$(\mathcal{L}' \times \mathcal{R})_i$ similar with extending $R$ and $(\mathcal{L}' \times \mathcal{R}')_i$ similar with extending both $L$ and $R$.

Needless to say, this is not very nice. This is because the problem does not lend itself to dynamic programming very well: you can not combine many partial solutions because there is no nice total ordering on the points, and you can not discard intermediate results for the same reason.


A nicer view on the problem is to model the set of points as weighted directed acyclic graph $G = (V, E, w)$ with

  • $V = \{(0,0), p_1, \dots, p_n, (X,Y)\}$ with $X = \max x_i$, $Y = \max y_i$, and
  • $E = \{ ((x_1, y_1),(x_2,y_2)) \in V^2 \mid x_i \leq x_j, y_i \leq y_j\}$ and
  • $w(v_1,v_2) = \begin{cases} 0 &, v_2 = (X,Y) \\ 1 &, \text{ else}\end{cases}$.

Note that you can keep the graph smaller if you remove redundant edges, that is remove $(v_1,v_2)$ if there is a path $(v_1,\dots,v_2)$, because taking such "shortcuts" is never better advantageous.

For one path, the solution is clearly the length of the longest path $P^*$ from $(0,0)$ to $(X,Y)$. Now, if we change $w$ so that all edges leading to points on $P^*$ also have weight $0$ and compute the longest path in this modified graph, we get a path $P^+$ so that $P^*$ and $P^+$ together cover as many points as two paths can. This leaves us with a runtime in $O(|V| + |E|) \subseteq O(n^2)$ (see here).

$\endgroup$
  • $\begingroup$ I may have misunderstood what you wrote, but for the weighted directed acyclic graph, does that mean we can simply find the longest path first, then delete all the edges in the longest path and find the longest path in the remaining graph? $\endgroup$ – Aden Dong Jul 1 '12 at 2:42
  • $\begingroup$ @AdenDong: No, not delete; the second path is allowed to reuse edges the first path took. We assign them weight $0$ so their target nodes are not counted again -- we want the second path to take a new route if profitable, after all. $\endgroup$ – Raphael Jul 1 '12 at 9:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.