### Dark_Soul031's blog

By Dark_Soul031, history, 2 weeks ago,

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.

• +1

 » 2 weeks ago, # |   0 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 valuenow 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 answerelse 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)
 » 2 weeks ago, # |   0 in Q2 you are probably saying elements of array can only have 3 possible values and 1<=zi<=3we know that priority of zi=1>zi=2>zi=3so we will maintain a priority array with max priority stored corresponding to any indexlets say xi to yi demand zi=2so 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 problemdp[0]=1;for i in 1 to Ndp[i]=dp[i-1]*priority[i]
•  » » 2 weeks ago, # ^ |   0 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...?
•  » » » 2 weeks ago, # ^ |   0 nothe 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