Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Dark_Soul031's blog

By Dark_Soul031, history, 2 hours ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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)