Why's my Convex Hull Trick so Slow?

Revision en3, by minimario, 2017-09-25 05:52:54

Hi all,

I was solving this problem: Link. It's fairly easy, so if you don't really want to solve it, I'll go ahead and write the dp recurrence here:

dp[i][k] = max(dp[j][k - 1] + p[j] * (p[i] - p[j]))

A pretty obvious Convex Hull Trick (CHT) problem. But I'm getting TLE on the last test case. I opened some AC codes, and I didn't see much difference between our codes, so I'm wondering what makes mine so slow and the other one so fast!

436 ms code

My submission

If anyone has some insights, please comment (or PM me) with details!

(P.S.: If anyone has a fairly fast implementation of CHT that would like to challenge the 436 ms, go ahead and submit it :))

Thanks so much,

-minimario

Tags cht, optimization, apio

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English minimario 2017-09-25 05:52:54 34 Tiny change: ' obvious CHT problem. ' -> ' obvious Convex Hull Trick (CHT) problem. '
en2 English minimario 2017-09-25 05:34:57 180
en1 English minimario 2017-09-25 05:34:16 657 Initial revision (published)