NgVietDuc's blog

PLS HELP ME,IM JUST A STUDENT WITH NO EMPLOY
By NgVietDuc, history, 2 days ago, In English

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

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

»
2 days ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    46 hours ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    ok

    → Reply
»
45 hours ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
41 hour(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
31 hour(s) ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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).

→ Reply