Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

adamant's blog

By adamant, history, 11 months ago, In English,

Hi everyone!

Perhaps you heard about github project on translating e-maxx. The thing is that project is actually more than just translating it. You see, there are bunch of algorithms and approaches which either do not have proper elaborations or have but they're written in some weird uncommon languages like, you know, russian or chinese. And there are some sites which just don't fit for this purpose for some reasons.

Years ago when I started doing competitive programming e-maxx.ru was the main resource to learn things. Things changed a bit now. E-maxx is Russian only and it wasn't updated for years. And now I hope that e-maxx-eng will manage to fill this gap of common resource for everyone to learn new things and keep updated on recent competitive programming tricks and new algorithms.

So I encourage everyone to collaborate in making e-maxx-eng comprehensive guide into competitive programming, and not only on hacktoberfests :). And to begin with I would like to share with you my article on convex hull trick and Li Chao tree I wrote for this resource. Enjoy!

If you were too lazy to read it thoroughly: There is a link to CHT and Li Chao tree article just above this sentence!

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

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Oh, I totally forgot, if you have any topics on which you would like to get an article, you can write it here :)

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    1. Ji Driver segment tree
    2. Gomory Hu trees
    3. Maybe some math serious topic.
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    SGT Beats use of segment tree(mentioned here).

    Also, I think your article should mention that Li-chao can easily be extended for parabolic functions much easily(useful for problem KILLER)

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, I mentioned that it only assumed that each pair of functions intersects at most once..

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (O(n), O(1)) RMQ algorithm by Fischer and Heun (link).

»
11 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

WPS Binary Search

(or I guess it is also called Lagrange optimization in section 5 of this article)

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

On behalf of all newbies like me I really thank you! Looking forward for more articles!

»
10 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Here's a straightforward dynamic CHT/Li Chao tree problem if anyone wants to test their template: https://csacademy.com/contest/archive/task/squared-ends

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

It is first time to hear about Li Chao tree, it is so awesome and easy to code ^_^

However if the numbers are very large, we can use ranking (instead of dynamic segment tree) as it will save space, memory and easier to code (as the code will be the same, only difference is instead of calling f(x), we call f(rev_rnk[x])), however this works only in offline queries (since we need to rank both input and numbers in queries).

Thank you for the nice article :)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the great article adamant! Just to notice, the images/figures on the article are broken.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    adamant I'll look into it. Looks like all images are broken on e-maxx-eng.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Are exercise problems sorted in increasing order of difficulty?