Problem links:
Contest
Practice
Difficulty:
Medium-Hard
Prerequisites:
Simple Dynamic Programming.
Problem:
We are given an array of ‘n’ unique integers.We need to find the difference between number of increasing sub-ranges and number of decreasing sub-ranges for every continuous sub-array of length k from left to right and output the sum of these differences.
Explanation:
Store the numbers in an array,say A.
We need to maintain two arrays for this purpose. B and C,where
B[i]=number of increasing subranges ending at ith element A[i] (contribution of ith element to number of increasing subranges)
C[i]=number of decreasing subranges ending at ith element A[i] (contribution of ith element to number of decreasing subranges)
Step 1: Generate B and C. B and C are filled in this manner.
B[i]= { B[i-1]+1 if A[i]>A[i-1]
{ 1 otherwise or i==1
Step 2:Generate L_B and L_C.
L_B is the array that contains the length of increasing sub-arrays in A.
L_C is the array that contains the length of decreasing sub-arrays in A.
Example:
A: 1 2 3 4 7 5 6
B: 1 2 3 4 5 1 1
L_B: 5 1 1
the length of first increasing sub-array is 5 next is 1
C: 1 1 1 1 1 2 3
L_C: 1 1 1 1 3
the length of first decreasing sub-array is 1 next is 1 and the last is 3.
Step 3:Calculate the difference between number of increasing and decreasing sub-ranges from 1 to k.
increasing sub-ranges inc=sum of B[i] for i=1 to k.
decreasing sub-ranges dec=sum of C[i] for i=1 to k.
answer= difference of increasing and decreasing sub-ranges.
Step 4:Keep Sliding the window 1 step forward i.e add the next element and remove the first element and calculate the no. of increasing and decreasing sub-ranges accordingly.
Example :
for next window:
inc+=b[k+1]-b[1]
dec+=c[k+1]-c[1]
inc and dec will now contain the sum of B[i] and C[i] respectively for the next window of length k.
inc and dec might not be the actual values as we have removed the first element which might be contributing to the rest of series.Hence, we need to subtract something to get the actual values.
For example:
n=4
k=3
A: 1 2 4 3
B: 1 2 3 1
for i=1 to 3
inc=6
for i=2 to 3 inc=2+3+1=6 i.e not true, as 2 and 3 should be 1 and 2,if it was independent of the first element.
If first element is not 1,we need to subtract the removed element from the increasing sub-ranges until next 1 has occurred or the series has ended. i.e the times we need to subtract is the length of the current increasing sub-range or k times respectively.
If the starting element would have been 1. The output would be correct, as the removed element wouldn’t be contributing anything to the increasing sub-ranges. Also if it is 1 that means the last increasing sub-range has ended and next one has begun. Hence, the next time we need to subtract the removed element we will do it L_B[++j] times,where L_B is the length array.
Hence the algorithm reduces to:
for i=k+1 to n
inc+=b[i]-b[i-k]
inc2=inc
if(b[i-k+1]==1)
j++
else
if(b[i]-b[i-k+1]+1==k)
inc2-=b[i-k]*k
else
inc2-=(b[i-k])*(l[j]-b[i-k+1]+1)
Similarly,calculate the same for dec and subtract these 2 for each sub-range of length k and output the sum of these.
Solutions:
Author’s solution can be found here.