Codeforces Round #278 Problem D. Strip.

Правка en3, от blank_manash, 2020-07-10 22:46:57

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский blank_manash 2020-07-10 22:46:57 1441 Tiny change: 'works.\n\n' -> 'works.\n\n=============\n'
en2 Английский blank_manash 2020-07-10 19:55:50 4 Tiny change: 're $k \in (i-g[i],i-l)$\n\nAnd $' -> 're $k \in [i-g[i],i-l]$\n\nAnd $'
en1 Английский blank_manash 2020-07-10 19:55:10 576 Initial revision (published)