### Kuhhaku's blog

By Kuhhaku, history, 5 weeks ago, ,

Can Some Explain on How to solve this problem. 488D - Strip

I understood the recurrence relation given in the editorial but I do not know understand how to use Sparse Table or Segment Tree ( Or the Monotonic Queue ) to calculate the function $f[i]$ and $g[i]$.

According to the recurrence $f[i] = min(f[k])+1;$ where $k \in [i-g[i],i-l]$

And $g[i]$ is the greatest length of the sequence ending ( and including ) at $i$ and satisfying the properties.

How will we Calculate $g[i]$ and $f[i]$ ?

Update : I Got it. Maybe I'll give a brief description of how it works.

==================================================================================

Solution.

Suppose we had a Data Structure that could give us the minimum in a dynamic range. Now, for calculating the function $g[j]$ let's iterate over right to left. Since $g[j]$ denotes the minimum $i$ ( and hence maximum length ) such that the range $\in [i,j]$ satisfies the condition $max_{i,j}-min_{i,j} \leq s$. We the observe the following structure.

$g[j-1] \leq g[j]$

Proof.

Let's say $g[j] = i$, now to calculate $g[j-1]$ ( i.e Removing the jth element) 3 cases arise.

• $jth$ element is $max_{i,j}$,

• $jth$ element is $min_{i,j}$,

• None of these.

The last case won't affect the situation and since we the interesed in $max_{i,j-1} - min_{i,j-1}$ we can observe in either of the first two cases $max_{i,j-1}$ will decrease or $min_{i,j-1}$ will increase. Hence $g[j-1]$ will be atmost equal to $g[j]$.

This inequality gives in the impression of using the two pointers technique and hence $g[i]$ can be calculated in amortized $O(n)$. Now for calculating $f[i]$, it's the minimum in the range $\in [i-g[i],i-l] + 1$ which directly translates into sliding window mininum.

You can use a Segment Tree or Monotonic Queue to find the minimum and maximum in a running window.

• +1