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, In English,

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.

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by overACer (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by overACer (previous revision, new revision, compare).