2
$\begingroup$

Given a sequence of pairs $(a_1, b_1), (a_2, b_2), ..., (a_n, b_n)$ such that $a_1 \le a_2 \le ... \le a_n$ (i.e, sorted in ascending order by $a$'s), we solve the longest increasing subsequence problem for $b$'s. Now suppose the length of the longest increasing subsequence is $X$.

If we now sort the initial sequence by the second component and solve the LIS problem for $a$'s, is the length of this sequence also equal to $X$?

Intuitively I think this is true, but I don't know if it really is.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Have you tried proving it? $\endgroup$
    – Yuval Filmus
    Sep 20, 2017 at 14:37

1 Answer 1

Reset to default
1
$\begingroup$

When you solve the longest increasing subsequence problem in its original formulation, you are finding the longest sequence $i_1,\ldots,i_\ell$ such that $$ a_{i_1} < \cdots < a_{i_\ell} \\ b_{i_1} < \cdots < b_{i_\ell} $$ This holds even if you shuffle the indices. Since the object you are maximizing is symmetric in the $a$s and $b$s, you will get the same length in both cases.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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