[GeeksforGeeks]Largest subsquare surrounded by X

by zkw, Jul 18, 2016, 3:08 PM

This is an $O(n^2)$ approach. Let $a(x,y,d)$ be the maximal length of $\texttt{X}$ starting from $(x,y)$ and going to direction $d$. Let \begin{align*} b(x,y) & =\min\big\{ a(x,y,\text{right}),a(x,y,\text{down})\big\}\\ c(x,y) & =\min\big\{ a(x,y,\text{left}),a(x,y,\text{up})\big\}\ , \end{align*}then the answer should be $$ \max\Big\{ z:\exists x,y\text{ s.t. }z\le\min\big\{ b(x,y),c(x+z,y+z)\big\}\Big\}\ . $$Divide the problem with different $x-y$, and this becomes an 1D problem. Given two arrays $\mathbf{a}$ and $\mathbf{b}$, try to pick an index $i$ from $\mathbf{a}$, and $j$ from $\mathbf{b}$, such that $j<i+a[i]$ and $j-a[j]<i$, which leads to the maximal $j-i$. Let $v[\mathbf{a}]$ be the set of all intervals $\big[i,i+a[i]-1\big]$, and $v[\mathbf{b}]$ be the set of all intervals $\big[j,j-a[j]+1\big]$. It is easy to find that if an interval in $v[\mathbf{a}]$ is covered by another interval in $v[\mathbf{a}]$, then it is useless. So we can sort all intervals in $v[\mathbf{a}]$, such that the left ends and right ends are both increasing, and the same as $v[\mathbf{b}]$. For each intervals $[p,q]$ in sorted $v[\mathbf{b}]$, discard all intervals $[r,s]$ such that $r<p$ or $s<q$ in $v[\mathbf{a}]$, and updates the answer accordingly.
Program (in C++)
This post has been edited 2 times. Last edited by zkw, Jul 18, 2016, 3:11 PM

[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

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