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

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

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

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

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

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

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

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

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

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

»
7 дней назад, скрыть # |
 
Проголосовать: нравится +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).

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

    So that means Convex Hull Trick doesnt have optimal optimal point ascending?

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

      CHT doesn't require monotone opt, unlike D&C. It only needs the transition to be a line. If slopes and queries are sorted, opt does move in one direction, so a deque gives O(N). If not, binary search the hull or use a Li Chao tree.

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

        Ok ty bro