I had a dream about a problem last night that I still haven't been able to solve. Maybe The community can give some insight.

Problem Statement.

You're given an array $$$a$$$ of size $$$n$$$, You perform the following steps in a single operation :

0) Take $$$i = 0$$$,

1) Let $$$j$$$ be the minimum index $$$(j > i)$$$ such that $$$a[j] > a[i]$$$

2) Delete the element $$$i$$$ from the array.

3) If $$$j$$$ doesn't exists, terminate the operation, else set $$$i = j$$$ and repeat from 1.

You are required to find the number of operations you can perform before the array is empty.

An $$$\mathcal{O}(n^2)$$$ algorithm is quite visible, but can you solve it in approximate linear time ?

I'm familiar with the frequent topics in Competitive Programming. But I seem to get lost even in some of the typically easy constructive problems. Even if some of the times I do get an Idea on how to solve it, I can't build any convincing proof on it, which makes it difficult to recognize in which cases my idea would be failing ( Or if even if it's correct ).

Most of the times I read the editorial, and I do understand it but I do not know how if I can reproduce that idea in the future and more of feels like a game of luck.

How do you approach constructive problems and how can I improve on it ?

Any Valuable Suggestions Are Appreciated.

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.