Codeforces Round #278 Problem D. Strip.

Revision en2, by blank_manash, 2020-07-10 19:55:50

Can Some Explain on How to solve this problem. https://mirror.codeforces.com/contest/487/problem/A

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]$$$ ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English blank_manash 2020-07-10 22:46:57 1441 Tiny change: 'works.\n\n' -> 'works.\n\n=============\n'
en2 English 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 English blank_manash 2020-07-10 19:55:10 576 Initial revision (published)