Bekh's blog

By Bekh, history, 6 weeks ago, In English,

I've been learning about Aliens dp trick from here: and I had a few doubts about it.

1- In the pseudocode section in the blog. If we're solving the problem for exactly $$$k$$$ instead of less than or equal to $$$k$$$, will we have to include negative penalty values in the binary search range as we might need to move in both directions of the optimum point?

2- Regarding the reconstruction issues section.

What I've understood (kinda) is that if our function is not strictly convex (i.e. might look something like the image below), No penalty value will ever get us a value between $$$a$$$, and $$$b$$$. I've also understood that if our binary search could get us $$$a$$$ (Our best effort for the greatest value less than or equal to $$$k$$$), then $$$ans[k] = ans[a] + (k - a) * t$$$ where $$$t$$$ is the step of the arithmetic progression (Since the function is linear between $$$a$$$, and $$$b$$$). I don't understand how we reached $$$ans[k] = ans[a] - (k - a) * penaltyValue$$$ from that. (The equations in the blog are using $$$p$$$ instead of $$$a$$$).

  • Vote: I like it
  • +5
  • Vote: I do not like it