Codeforces Round #278 Problem D. Strip.

Правка en1, от blank_manash, 2020-07-10 19:55:10

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

История

 
 
 
 
Правки
 
 
  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)