Problem: 1D dp speedup: (http://dmoj.ca/problem/cco19p4)↵
↵
This dp satisfies the property $dp[i]=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)?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.↵
↵
↵
↵
↵
↵
↵
↵
This dp satisfies the property $dp[
↵
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.↵
↵
↵
↵
↵
↵
↵
