You have a sequence of N elements H1,H2…HN. A climb is defined by the nonempty sequence (p1, p1+1), (p2, p2+1), …, (ps, ps+1), where pk+1 ≤ pk+1 for k = 1, 2, …, s − 1.
Two climbs, say (p1, p1+1), (p2, p2+1), …, (ps, ps+1) and (q1, q1+1), (q2, q2+1), …, (qt, qt+1) are different if and only if
- s ≠ t or
- There exists at least one k such that 1 ≤ k < min(s, t) and Hpk+1 – Hpk ≠ Hqk+1 – Hqk.
If you read the problem carefully and is thought over for sometime you’ll realise the basically what is asked for is number of different/distinct subsequences of the sequence H2-H1,H3-H2…HN-HN-1.
So, our problem is reduced to: Given a sequence A1,A2…AN, find the number of distinct subsequences. Subsequence is a sequence that can be derived from sequence A by deleting some elements without changing the order of the remaining elements. Two subsequences are distinct if there length are different or some of the corresponding element is different.
dp[i] = Number of distinct subsequences ending with A[i].
sum[i] = dp + dp + … + dp[i]. So sum[n] will be our answer.
last[i] = last position of occurence of A[i] in the array A.
A null string has one subsequence, so dp = 1.
for i=1 to N: dp[i]= sum[i-1] - sum[last[a[i]]-1] sum[i]=sum[i-1] + dp[i] last[a[i]]=i print sum[n]
Initially, we assume we can append A[i] to all subsequences ending on previous characters, but this might violate the condition that the counted subsequences need to be distinct. Remember that last[A[i]] gives us the last position A[i] appeared on until now. The only subsequences we overcount are those that the previous A[i] was appended to, so we subtract those.
Using map in C++ to store last would have timed out. It was intentional. Also, take care of modulo operations.
If all elements in A are distinct, our answer will be 2N. Let’s say dp[i] stores the answer for array A_1 to A_i. Now, if there is some i<j such that A[i]==A[j], we should consider only last occurence of A[j] ie. at the index i. So we have to subtract the number of subsequences due to it’s previous occurrence.
This pseudo code will make it more clear:
dp=1 // for length 0 the subsequences are 1 for i=1 to N: dp[i]=dp[i-1]*2 if A[i] has occured last time at index j: dp[i]=dp[i]-dp[j-1] print dp[n]
AUTHOR’S AND TESTER’S SOLUTIONS:
Note: Editorial inspired from a post on stackoverflow.