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

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

Can sb tell me about how to optimize dp with DnC and Convex Hull Trick and pls differenciate two algorithm

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

»
2 недели назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

DnC and Convex Hull Trick is not that important if you only want to participate in VOI lol bro

»
2 недели назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Convex hull trick (and LiChao)
DnC trick
They are completely different.

»
2 недели назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

perhaps it`s worth at least reading some articles about these algorithms before asking questions about them

»
2 недели назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Both speed up DP transitions that would normally be O(N^2), but they work in different ways.

D&C relies on the fact that the best split point only moves right as you go forward. So you solve the middle position first by checking all candidates, then solve the left half using only candidates to the left of that best point, and the right half using only candidates to the right. This brings each layer down to O(N log N). It works for layered DPs like "split an array into K groups" where the cost is some function of a range.

Convex Hull Trick relies on the formula itself. If the transition can be rewritten so each old state is a straight line, then computing a new state just means finding the lowest (or highest) line at a given x. You only keep the lines that matter, and with sorted slopes and queries it runs in O(N).