PROBLEM LINK:
DIFFICULTY:
Easy-medium
PRE-REQ:
Dynamic Programming
PROBLEM:
A “Zig-zag” sequence is a sub-subsequence of odd length and if it starts with integer x, every odd positioned element needs to be x. Each even positioned element can be either x + 1 or x - 1.
Given a sequence A_1, A_2, ..., A_N, count number of zig-zag sub-sequences in it. Two sub-sequences are different if any of the index is different in them.
EXPLANATION:
================
We define f(i, j, k) as number of sub-sequences of A_1, A_2, ..., A_i, ending at value j and k denotes three cases:
- k = 0 denotes that last element chosen was in odd position of the sub-sequence
- k = 1 denotes that last element chosen was in even position and its value was x+1, where x is value of odd indices
- k = -1 denotes that last element chosen was in even position and its value was x-1, where x is value of odd indices
Now, we can define recurrences as:
- f(i, A_i, 0) = f(i, A_i, 0) + 1 + f(i-1, A_i+1, 1) + f(i-1, A_i-1, -1), since all previous sub-sequences are valid and we get a new sub-sequence(only A_i) and we also account for previous sub-sequences whose odd positioned element could be A_i-1 or A_i+1.
- f(i, A_i, 1) = f(i-1, A_i, 1) + f(i-1, A_i-1, 0), since we add also those sub-sequences where A_i-1 was odd positioned.
- f(i, A_i, -1) = f(i-1, A_i, -1) + f(i-1, A_i+1, 0), since we add also those sub-sequences where A_i+1 was odd positioned.
Eventually, to our answer we add those values f(N, j, k) such that k=0.
Now, note that we can build the DP table on the go and there is no need for actually maintaining different tables for all i. Also, since values can be upto 10^9, so we maintain a hash map of with a pair of \{value, flag\} as key and f(value, flag) as the value.
Total number of states we access is O(N) in worst case. So, total complexity is O(N).