[LeetCode] Guess Number Higher or Lower II

by zkw, Jul 17, 2016, 4:13 PM

First, here is a trivial DP solution with $O(n^{3})$. Let $f(a,b)$ be the minimum worst-case cost to guess a number $a\le n\le b$, then we have $$ f(a,b)=\min_{a\le k\le b}\Big(\max\big\{ f(a,k-1),f(k+1,b)\big\}+k\Big)\ . $$Enumerate $k$ and we are done. To optimize the computation, let $$ k_{0}(a,b)=\max\{k:f(a,k-1)\le f(k+1,b)\}\ , $$then \begin{align*} & \max\big\{ f(a,k-1),f(k+1,b)\big\}\\ = & \begin{cases} f(k+1,b) & \text{if }a\le k\le k_{0}(a,b)\\ f(a,k-1) & \text{if }k_{0}(a,b)<k\le b \end{cases}\;. \end{align*}Therefore, \begin{align*} f(a,b) & =\min\big\{ f_{1}(a,b),f_{2}(a,b)\big\}\\ f_{1}(a,b) & =\min_{a\le k\le k_{0}(a,b)}\big(f(k+1,b)+k\big)\\ f_{2}(a,b) & =\min_{k_{0}(a,b)<k\le b}\big(f(a,k-1)+k\big)\\ & =f\big(a,k_{0}(a,b)\big)+k_{0}(a,b)+1\ . \end{align*}Notice that $k_{0}(a_{1},b)\le k_{0}(a_{2},b)$ when $a_{1}\le a_{2}$. So we can compute $k_{0}(a,b)$ in amortized $O(1)$ time. Then we need the sliding minimum of $g(k,b)=f(k+1,b)+k$ with $b$ fixed and $a\le k\le k_{0}(a,b)$. This can be done using an increasing deque, and it takes amortized $O(1)$ time to get the desired minimum. We need to compute $O(n^{2})$ values of $f$, and each takes $O(1)$ time, so in all $O(n^{2})$.
Program (in C++)
This post has been edited 10 times. Last edited by zkw, Jul 21, 2016, 9:46 AM

Comment

1 Comment

The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Can you help to solve rotate matrix problem from Interviewbit?

by codo0, Aug 18, 2018, 11:46 AM

avatar

zkw
About Owner
  • Posts: 25
  • Joined: Jun 21, 2007
Blog Stats
  • Blog created: Jul 17, 2016
  • Total entries: 2
  • Total visits: 5628
  • Total comments: 1
Search Blog
a