{"id":2184,"date":"2020-07-29T08:31:56","date_gmt":"2020-07-29T08:31:56","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2184"},"modified":"2022-03-30T22:55:17","modified_gmt":"2022-03-30T22:55:17","slug":"rahul-and-puzzle-world","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/rahul-and-puzzle-world\/","title":{"rendered":"RAHUL AND PUZZLE WORLD"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Dynamic programming<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(SIMPLIFIED):<\/h3>\n
\n

For each query , give the size of maximum square with all pictures i.e. all ones from the given matrix of 1s and 0s.<\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
5 5\n0 0 0 0 0\n1 1 1 1 0\n1 1 1 1 0\n1 1 1 1 1\n0 0 0 0 0\n5\n4 4 5 4\n3 3 3 4\n3 1 3 3\n2 3 3 4\n2 1 5 4\nFor the 1st query, from (4,4) to (5,4) a square of size 1 is formed with all 1\u2032s.\nFor the 2nd query, from (3,3) to (3,4) a square of size 1 is formed with all 1\u2032s.\nFor the 3rd query, from (3,1) to (3,3) a square of size 1 is formed with all 1\u2032s.\nFor the 4rth query, from (2,3) to (3,4) a square of size 2 is formed with all 1\u2032s.\nFor the 5th query, from (2,1) to (5,4) a square of size 3 is formed with all 1\u2032s.<\/code><\/pre>\n
<\/strong><\/u><\/a><\/p>\n
SOLVING APPROACH:<\/h3>\n
\n
First lets calculate dp[i][j] \u2014 maximum square ending in cell ( i, j). For each cell if input matrix contain 0 then dp[i][j]\u2009=\u20090 else dp [i][j]\u2009=\u2009min( dp[i\u2009-\u20091][j\u2009-\u20091], dp[i\u22121][j], dp[i][j\u22121])\u2009+\u20091.<\/p>\n
We will use binary search to find the answer. Lets fix some value x. For each square ( i, j)..( i\u2009+\u2009x\u2009-\u20091, j\u2009+\u2009x\u2009-\u20091) we need to find maximum and compare it to x. To find maximum we can use 2D sparse table.<\/p>\n<\/blockquote>\n
In simple words-<\/strong><\/p>\n
\n
    \n
  1. Give you a 0-1 matrix, then Q queries, each time you query a rectangular area, the maximum length of a square is the largest one.<\/li>\n
  2. First consider Dp, dp[i][j]<\/code> indicates that the (i,j)<\/code> position is the lower right corner, and the maximum square side length is, obviously dp[i][j]<\/code> = min(dp[i-1][j ], dp[j][i-1], dp[i-1][j-1])+1<\/code>.<\/li>\n
  3. Then, after we made this decision, what would we do?<\/li>\n
  4. Direct two-point answer, assuming that our two-point answer is mid, obviously the point in the upper left corner of this rectangular area is the waste point, and then query the maximum value of the remaining points, whether it is greater than or equal to m.<\/li>\n
  5. This can be done with binary search.<\/li>\n
  6. We will use binary search to find the answer. Let’s fix some value x. For each square ( i, j)..( i\u2009+\u2009x\u2009-\u20091, j\u2009+\u2009x\u2009-\u20091) we need to find the maximum and compare it to x. To find the maximum we can use a 2D sparse table.<\/li>\n<\/ol>\n<\/blockquote>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t