UVA 11654 - Arithmetic Subsequence

http://uva.onlinejudge.org/external/116/11654.html

You are given a set of given a set of integers, determine how many proper subsets of this set form an arithmetic sequence. 

For those that forgot what is an arithmetic sequence (or arithmetic progression), is a sequence such that the difference between successive elements is constant. For example, \(\{2, 4, 8, 10\}\) is an arithmetic sequence where the constant different of each element is two.

It is always a good idea to verify if the brute force solution (if any) runs under the time limit. The idea behind the brute force approach is to generated all possible subsequence of the given set, and check whether or not is an arithmetic sequence. Is not hard to see, that the constraints are way to high for this solution, \(N\) can reach up to 250, which means that we can have \(2^{250}\) subsets, in other words not possible under the 5 seconds time constraint.  

To solve this problem we need to do reduced from exponential time complexity to linear, this is when Dynamic Programming comes into play. 

First let's make some observations about the arithmetic sequences. It is always possible to create all the size one and two subsequences for any given set. This means, the answer is always at least \(\frac{N + N(N-1)}{2}\). Knowing this, the idea behind the DP solution is to first pick some sequence of two elements which ends points are the index \(i\) and \(j\). After we do this, we tried to extend this subsequence checking if there is any subsequence ending at index \(k\) that we can connect with our current one. In order to be able to connect a subsequence with another one the difference between their successive elements must be equal, as the definition of arithmetic sequence establish.

The overall time complexity of this solution is \(O(N^{3})\).