Wednesday, August 27, 2014

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.