## Tuesday, July 22, 2014

### a bit of uva : UVa 11572 - Unique Snowflakes

Problem Statement:
UVa 11572 - Unique Snowflakes

Summary:
Find the maximum $$|i-j|$$ such that for a sequence $$a_1,a_2,\ldots,a_n$$, the subsequence $$a_i, a_{i+1}, \ldots, a_j$$ has distinct elements.

I like this problem, because it allows you to think a bit and reward you with happiness and joy (haha wth I'm writing that for). Strategy: Suppose we already have a subsequence $$T = a_i, a_{i+1}, \ldots, a_j$$. Upon deciding whether $$a_{j+1}$$ can be added to this subsequence, we need a quick way to check whether the previous occurrence of $$v = a_{j+1}$$ is before index i. Otherwise it's already in the subsequence, and therefore if there is a longer subsequence other than T, it must start after the occurrence of v in T (Proof by contradiction). By the end of this procedure, we will obtain the longest subsequence possible such that each element are all distinct.

There are various ways to get a fast look up for previous occurrences of an element: If $$a_i$$ are small, a simple array for direct addressing table (DAT) suffices. Otherwise, a good hash table with expected O(1) or a map with O(log N) look-up time will do.