Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### overACer's blog

By overACer, history, 5 weeks ago, , Problem: 1D dp speedup: (http://dmoj.ca/problem/cco19p4)

This dp satisfies the property

$dp[j]=max_{i<j} (dp[i]+C[i][j])$

, where

$C[i][j]$

satisfies quadrangle inequality. How can I optimize to O(n log n) or O(n)?

Outline: since all queries are sorted in ascending order, I can do it with convex hull and binary search (if k=3). This gives O(n log n).

How binary search is done:

Fix

$i<k<j$

, we compare

$dp[i]+C[i][j]$

with

$dp[k]+C[k][j]$

Note

$C[i][j]=(prefix[j]-prefix[i])^{\frac{k}{2}}$

. It grows faster than

$C[k][j]$

. In fact,

$(prefix[j]-prefix[i])-(prefix[j]-prefix[k])$

is an invariant, call $x$. Let

$y=dp[k]-dp[i]$

. Rewrite

$C[k][j]=z, C[i][j]=z+x$

.

Consider $(a,b)$ such that

$a^{\frac{3}{2}}-b^{\frac{3}{2}}=y$

, and

$a-b=x$

. The precise solution would use sqrt, and would take O(log n) anyways (to an error of $10^{-6}$, might raise if TLE). (Am I wrong?) Note $a$ corresponds to

$C[i][j]$

and $b$ corresponds to

$C[k][j]$

, even though they might never be equal to those values. Then for all

$C[i][j]>a$

,

$dp[i]+C[i][j]>dp[k]+C[k][j]$

and for all

$C[i][j]<a$

,

$dp[i]+C[i][j]<dp[k]+C[k][j]$

Is this correct? Implementation looks rly hard.  Comments (2)
 » Auto comment: topic has been updated by overACer (previous revision, new revision, compare).
 » Auto comment: topic has been updated by overACer (previous revision, new revision, compare).