Why's my CHT so Slow?

Revision en1, by minimario, 2017-09-25 05:34:16

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 CHT problem. But I'm getting TLE on the last test case. I don't see much difference between our codes, so I'm wondering how it could be so slow!

436 ms code My submission

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

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)