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.

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