The Curse of Segment Tree

Правка ru1, от limbo16, 2024-03-18 12:33:57

Hi guys! Today I had an exam on algorithms and data structures, where one of the tasks was to write down an algo for finding longest common increasing subsequence in $$$O(n^2)$$$ (yeah, using pen and paper...) For whatever reason, I came up with only $$$O(n^2logn)$$$ solution. However, this solution could be easily simplified to $$$O(n^2)$$$ and many students from my course wrote this algorithm. I guess it happened because when you don't know segtree it is much easier to avoid wrong paths and reach good solution.

Then I caught myself on the thought that in many problems before I also implemented very dumb overkilled solutions with segment tree simply because I know this data structure (thank god I don't know treaps that well). Then I came up with the name of this phenomenon: "The Curse of Segment Tree". So I wonder have anybody also stumbled with this "curse"? (or I am the only orange guy who cannot come up with stupid dp on the uni exam TᴖT)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский limbo16 2024-03-18 12:35:28 972 Initial revision for English translation
ru1 Русский limbo16 2024-03-18 12:33:57 972 Первая редакция (опубликовано)