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

selfcompiler's blog

By selfcompiler, 6 years ago, In English,

Can anyone Guide me how to optimize this relation  where b[j]>=b[j+1] and a[i]<=a[i+1] .I know for optimization use convex hull trick and i read convex hull trick ,but i don't know how to use this trick to optimize this Dp relation.

  • Vote: I like it
  • 0
  • Vote: I do not like it

6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Well initially start with an empty set of lines, then after you calculate dp(i) add the line Ax+B witb A=b(i) and B=dp(i). Then if at some point you want to calculate dp(i) then you just run a query with x=a(i). The b(j)<=b(j+1) allows adding lines without using a dynamic set and a(i)<=a(i+1) allows solving the problem using pointer walk on the set of lines instead of doing binary each time, thus reducing the running time to amortized O(1) per query.

Sorry for using () instead of [] im writing from a phone.