Saturday, November 8, 2014

UVa Problem 481 - What Goes Up

Problem:

Solution:

This problem forced me to learn the $O(n \log n)$ algorithm for the longest increasing sub-sequence algorithm, and so I did.

Initially I wanted to think about the problem myself, here is what I thought. I think thought process is valuable to document down. At first, I peek at the solution, having understanding that in depth, I know a binary search is going on, but on what list?

The very first observation I have is that we need to binary search on a list of "values", not "index". The standard longest increasing sub-sequence algorithm is a "search" on the longest increasing sub-sequence we found before subjected to the condition that the last element of that sub-sequence is less than the value we are facing right now.

The second observation is that in order for binary search to work, the values must be sorted, but the previously found longest sub-sequences might not be sorted with the last element value, let's see an example for this

40, 10, 20.

The previously found sub-sequences are

{40},
{10},
{10, 20}

The sequence {40} is bad, there is NO case whatsoever we wanted to extend that sequence anymore. Extending the sequence {10} can do the same effect of having a sequence of length 2.

I thought, if I think hard enough, I will get to the answer. Well, but I didn't, I just read this link.

Once I have done with the reading, now I get the 'same' idea, that we should drop the sequence {40}, but I don't get previously is the invariant that 'longer sequence must have larger end values'. With that invariant, which is not hard to prove, we can use binary search to find the right sequence to extend.

- closed the link right away after I get the idea and implement myself. With some book-keeping we can also maintain a list of indices and parent pointers to extract the longest increasing sub-sequence as the following code.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=422

#include "UVa481.h"

#include <iostream>
#include <vector>
#include <algorithm>
#include <list>

using namespace std;

int UVa481()
{
vector<int> input;
while (true)
{
int value;
cin >> value;
if (cin.eof())
{
break;
}
input.push_back(value);
}

vector<int> parent;
parent.resize(input.size());
vector<int> active_sequence_ends;
vector<int> active_sequence_indices;

// Initialize
parent[0] = -1;
active_sequence_ends.push_back(input[0]);
active_sequence_indices.push_back(0);

for (unsigned int i = 1; i < input.size(); i++)
{
// Step 1: Find the active sequence
unsigned int index = lower_bound(active_sequence_ends.begin(), active_sequence_ends.end(), input[i]) - active_sequence_ends.begin();

// At this point - index is pointing to the element not less than input[i], which means we should
// Case 1: input[i] is the least element, active_sequence_ends[0] should be updated
// Case 2: input[i] can extend the sequence of length 2, so index should be 3 right now
// Case 3: input[i] is the maximum element, the longest element can be extended, so extend it
if (index == active_sequence_ends.size())
{
parent[i] = active_sequence_indices[active_sequence_indices.size() - 1];
active_sequence_ends.push_back(input[i]);
active_sequence_indices.push_back(i);
}
else
{
if (index == 0)
{
parent[i] = -1;
}
else
{
parent[i] = active_sequence_indices[index - 1];
}
active_sequence_ends[index] = input[i];
active_sequence_indices[index] = i;
}
}
cout << active_sequence_ends.size() << endl;
cout << "-" << endl;
int index = active_sequence_indices[active_sequence_indices.size() - 1];
list<int> result;
while (index != -1)
{
result.push_front(input[index]);
index = parent[index];
}
for (list<int>::iterator i = result.begin(); i != result.end(); i++)
{
cout << *i << endl;
}
return 0;
}