PROBLEM LINK:
Author: Sergey Nagin
Tester: Shiplu Hawlader
Editorialist: Praveen Dhinwa
DIFFICULTY:
Easy
PREREQUISITES:
dynamic programming, simple combinatorics.
PROBLEM:
Given an array A. You have to find number of sub-sequences of A which are not arithmetic progressions(AP).
EXPLANATION
As total number of sub-sequences in the array A will be 2 n (including the empty sequence),
Excluding the empty sequence, we will have 2 n - 1 sub-sequences.
So instead of finding number of sequences which are not arithmetic progressions, we will find number of sequences which are
arithmetic progressions and subtract it from 2 n - 1.
Terminology
AP is defined as a series of a, a + d, a + 2 * d, etc.
By difference of AP we mean d.
Number of APs in an array A
Notice the following the observation.
- Elements of the array lie between 1 to 100 inclusive.
- Due to previous condition, maximum difference of AP can be at most 100.
- Similarly, minimum difference of AP can be at most -100.
So the values of elements of the array are small. We will make use of this observation.
Let us say we iterate over the difference of the AP and try to count number of APs in the array having the given difference.
Number of APs having difference d in an array A
We will solve this problem by dynamic programming. Let dp[i] denote the number of AP’s ending at i and having difference equal to d.
So if our current number is equal to A[i], we need to
find all the positions j < i such that A[j] = A[i] - diff and we will take sum of dp[j] for those j’s. It is equivalent to extending the
APs ending at position j with the element at position i.
Hence dp[i] = 1 + sum_(j = 1 to i - 1) dp[j] such that A[j] = A[i] - diff
We are adding 1 for the case when our current number is the only number in the AP. (1 element is also an AP according to problem statement.)
Naively computing the above recurrence will take time equal to O(N 2 ) which is not going to pass in the given time. We need to optimize this.
Note that we can optimize this by maintaining a sum array where sum[x] will record sum of all the dp’s where the value of array elements was x.
Mathematically speaking, sum[x] = sum of all dp[i]'s such that A[i] = x.
After this, our dp will be.
Hence dp[i] = sum[A[i] - diff] + 1.
Now with this optimization, our dp computation will take O(N) time.
Note that we are doing slight over-counting in the APs of just one element. Each iteration of diff will count A element APs, Hence it will
amount to over-counting. For that we can simply remove n single elements APs in the iteration over diff variable. In the end, we can simply
add the n 1 element APs.
// I have not included mod operations in pseudo code, don’t forget to include them.
pseudo code:
ans = 0
for diff = -100 to 100:
make an array sum of size 100.
cur = 0
for i = 1 to N:
if (A[i] - diff >= 1 and A[i] - diff <= 100):
// fetch the content from the sum array.
dp[i] = sum[A[i] - diff] + 1
// update the sum array.
sum[A[i]] += dp[i].
cur += dp[i]
// Now we need to remove 1 element APs,
// because each iteration of diff will count 1 elements AP, hence it will lead to over counting.
ans += cur
ans -= n
// Now add the 1 elements AP
ans += n
// For finding non APs, subtract from 2^n - 1
ans = 2^n - 1 - ans.
Complexity
Overall complexity is O(200 * N).
As 200 is the maximum possible value of difference of arithmetic progression because each number lies in the range [1, 100].
For each difference value of AP, we are just doing a single pass over the array A, Hence O(N) time.