Блог пользователя Tet

Автор Tet, история, 4 года назад, По-английски

First of all this "Trick" is just for fun and it's actually slower than the normal implementation of RMQ with segment trees so do not use it if the time limit is tight.

I did some research and couldn't find any similar blog but don't hesitate to inform me if this has been mentioned before, I'll delete this blog. So let's start!

Assume you have to perform two types of queries on an array:

  1. Find a minimal ( or maximal ) element in a range.
  2. Increase the elements in a range by a given value.

There are a lot of ways to do this but let's assume that you will code a segment tree with three basic functions:

  1. A build function.
  2. An add function which increases the elements in a given range by a given value.
  3. A get function to find a minimal element in a given range.

Now this "Trick" is about getting rid of the get function ( or at least making it shorter ), assume you want to find a minimal element in a given range $$$[l, r]$$$, we all know that the one of the minimal elements in the whole array is stored in the root node of the segment tree, let's take advantage of that!

By simply adding a big enough $$$\infty$$$ to segments $$$[1, l-1]$$$ and $$$[r+1, n]$$$ we will ensure that the value stored in the root node is actually a minimal element in the range $$$[l, r]$$$. ( don't forget to undo the adding operation after answering the query! )

Additionally adding $$$\infty$$$ to a segment can also be interpreted as deleting that segment which is worth mentioning.

Thanks to Mehrdad_Sohrabi for inventing this "Trick" which he refers to by the name Sohrabi segment tree.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +269
  • Проголосовать: не нравится

Автор Tet, 4 года назад, По-английски

Hi everyone!

Since a ton of blogs are being posted everyday and let's say not all of them are worth reading ●︿● , I decided to write this blog so that we could agree on some proper formatting or at least get some advice from experienced users.

this is aimed to be a discussion

Points that I find important while writing a blog ( not that my opinion matters anyway (¬_¬) ):

  • use:

    • Italics for Titles, Foreign Words, and Proper Names. ( not just for making your text look better )
    • Simple English ( maybe some users aren't as good as you are )
    • Your brain to figure out if your text can be misinterpreted ( this blog is a good example )
    • A fresh topic as mentioned by CoffeeTime in here
    • Proper code formatting as said by vovuh in here
  • avoid:

    • Non-English or poorly written context ( probably like this blog ¯\_(ツ)_/¯ )
    • Wasting time without getting a point across
    • Bringing up topics that don't really concern the CodeForces community
    • Bolding stuff without a reason
    • Pinging people when it's unnecessary ( Ari takes an honorable mention for this part )
    • writing stuff that would be obvious if your IQ was above room temperature ( take my blog for an instance (ಥ﹏ಥ) )
  • don't forget to:

    • TURN YOUR CAPS LOCK OFF
    • (as Errichto suggested) DO NOT Say "sorry for my poor English", it's just a few seconds wasted for every reader. ⊙﹏⊙
    • Get your point across with as few words as possible without dropping any details
    • Preview your blog before posting it
    • Follow basic punctuation rules as mentioned by -is-this-fft- in here

Also this is my personal opinion, but I think that blogs like this have the most appropriate formatting ~(˘▾˘~)

Anyways that was all I could think of at the moment, If you have any point worth mentioning please comment it and I'll add it ASAP.

Thanks for wasting your time on my blog (〃⌒∇⌒)

P.S. : As far as I know, this topic has only been discussed 6 years ago in here

Полный текст и комментарии »

  • Проголосовать: нравится
  • +207
  • Проголосовать: не нравится

Автор Tet, история, 5 лет назад, По-английски

Hi CodeForces!
Problems below are sorted by difficulity, hope they will rocket up your coding ability...

note : special problems are tasks which are effective when solved without reading the tags(they might be a bit harder too).

If you have any recommendations feel free to mention them in the comments section.
This blog will be updated on a monthly basis.
Special thanks to MhdMohammadi, M_H_M, KMAASZRAA and X_emad_X for finding these problems.

Also some people have complained that -Morass- has written a blog on the same topic, well the only difference is that this blog will be updated on a regular basis and you can access fresh tasks via this blog.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +57
  • Проголосовать: не нравится