[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

Comment

0 Comments

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