Codeforces Round #277 (Div. 2) Problem E. LIS of Sequence

Follow Up to this post.

Problem Statement:
E. LIS of Sequence

Solution:
This problem is quite nice to think about :D. Before attempting this problem, it might be useful to have a knowledge beforehand on how to solve LIS problem in \(O(N\lg{N})\) complexity using binary search.

This problem is more or less an extension to that idea. First we have an array of stacks stack[i] which is initialized with the following conditions:
1. the size of the array is initially 1.
2. push \(a_1\) into stack[0], so stack[0] contains \(a_1\).
Now we iterate from \(a_2,\ldots\) onwards till the end of the elements:
1. find the position of the maximum element amongst all elements on top of the stacks such that \(a_i\) is equal or larger.
2. if such position exist, push our current \(a_i\) into that stack. Otherwise, we add a new stack (hence incrementing the size of the array by 1) and push \(a_i\) to that newly created stack.

a bit of uva: Trainsorting - An intereseting application of LIS

Problem Statement:
UVa 11456 - Trainsorting

Summary:
Given \( S = \{a_1,a_2, \ldots, a_n\} \) where all \(a_i\) are distinct integers, and a dequeue \(D\) (initially empty), and operations push_back, push_front (which push an element to the back or to the front of D) or skip (which skips the element, of course) performed on elements in S from left to right, find the maximum length of D such that the elements inside are in increasing order.

(I have the talent to turn the summary of the problem into a more confusing piece of crap haha)

To approach this problem, we need knowledge on Longest Increasing Subsequence (LIS) and its direct variant, Longest Decreasing Subsequence (LDS).

Let me describe the algorithm to solve this problem first:

let LIS[i] be an array which stores the longest increasing subsequence in [i .. N]
let LDS[i] be an array which stores the longest decreasing subsequence in [i .. N]
set ans = 0
For \(a_i\) in \(S\):
    Either use \(a_i\) as the pivot or not.
    If use \(a_i\) as pivot:
        \( \text{ans} = \max\{ans, \text{LIS[i]} + \text{LDS[i]} - 1 \} \)
    Otherwise skip \(a_i\) and never look back :P

In the end of the for loop, \(\text{ans}\) will be the longest \(D\) possible.

Proof for optimality of \(D\): WLOG, assume that \(D = D_i\) where \(D_i\) is the longest dequeue constructed using elements in [i .. N] only. Suppose (for the sake of contradiction) that we can append some additional elements to \(D_i\) using elements in [1 .. (i-1)] to form \(D'_i\), and let the element added with the smallest index be \(a_j\) (where \(j < i\)). Clearly \(|D'_i| > |D_i|\). However, we also have \(|D_j| \leq |D_i|\) where \(D_j\) is the longest dequeue constructible using elements in [j .. N]. This means that \(|D_i| \geq |D_j| \geq |D'_i| > |D_i|\), a contradiction. Hence \(D\) must have been optimal in the first place, which completes the proof on the correctness on the algorithm.