m8.pie's blog

By m8.pie, 4 years ago, In English

Imagine the situation when we want to find such $$$a_j$$$ for any $$$a_i$$$ which will satisfy this:

$$$a_i > a_j$$$
$$$i < j$$$

Thanks to shufl999dka we know solution for this task with $$$O(n)$$$ complexity.

Solution

Imagine now the situation, when we want to find such $$$a_j$$$ for any $$$x$$$ and $$$[l; r)$$$, which will satisfy this:

$$$a_j < x$$$
$$$l \leq j < r$$$
$$$j\;is\;less\;possible$$$

First solution I developed was $$$O(n\log^2{n})$$$ complexity and had such algorithm:

Solution

But thanks to MrDindows and bicsi we have solution with $$$O(\log{n})$$$ complexity.

Solution

It is possible to see this algorithms working on concrete task: 1237D - Balanced Playlist

Solution $$$O(n\log^2{n})$$$ complexity is 732 ms — 62741630

Solution $$$O(n\log{n})$$$ complexity is 77 ms — 62881402

If you have more efficient solution for any of these two tasks then write here in comments.

Full text and comments »

  • Vote: I like it
  • +18
  • Vote: I do not like it