1.Given array A of size n.A triplet i,j,k is interesting if for evey i<p<j A[p]<A[i] and A[p]<A[j] and for every j<q<k A[q]<A[j] and A[q]<A[k]. Among all such interesting triplets find the maxium distance between k and i.(N<1e5) (Google)
2.An array of size n can have 3 values lets call them A,B,C.There are R requirements which demands exactly zi distinct values between xi and yi ,all these are of course input for R lines. How many such arrays are possible N<=300,R<=300 (Rubrik)
Can anyone give some ideas to approach these questions.
make 2 arrays val_left and val_right representing the leftmost and rightmost element bigger than current element (-1 if any element does not satisfy the case )
now use 2 pointer from both sides, such that val_left[L] and val_right[R] is non -1 value
now compute max bw elements at index L and R (both exclusive) — if max is greater than both elements (at L and R) you got the answer
else whichever element is bigger than that max, update it with next possible answer (L++ or R-- such that new value of L and R is non -1)
in Q2 you are probably saying elements of array can only have 3 possible values and 1<=zi<=3
we know that priority of zi=1>zi=2>zi=3
so we will maintain a priority array with max priority stored corresponding to any index
lets say xi to yi demand zi=2
so in priority array from xi+1 to yi update min value of zi i.e. priority[i] = min(priority[i],zi)
now a simple dp problem
dp[0]=1;
for i in 1 to N
dp[i]=dp[i-1]*priority[i]
I think it fails for some test cases :
like consider xi,yi,zi as[(1,4,1),(4,6,3),(6,8,1)] your array will be [1,1,1,1,3,1,1,1] and gives answer as 3 but answer would be 6 right...?
no
the array will be [3,1,1,1,3,3,1,1]
and the answer will be 27
[A|B|C]^4 + [A|B|C] + [A|B|C]^3