I've been learning about Aliens dp trick from here: http://serbanology.com/show_article.php?art=The%20Trick%20From%20Aliens 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$$$).
yes, 3 years later, now im having same question like you, have you solve them, help me pls
This is not a valid aliens trick case. The slope is decreasing then increasing then decreasing again, which is not solvable by aliens trick.
thanks, and what about the first problems? what will we do when "<=k"