HackerRank: Mr K marsh
Mr K has a rectangular land (m x n). There are marshes in the land where the fence cannot hold. Mr K wants you to find the perimeter of the largest rectangular fence that can be built on this land.
In Problems of rectangular grids pre-calculation often help and so in this problem. Because this problem is concerned with continues points in a row/column not having any marsh it will be helpful to pre-calculate number of continues point up,down,left and right of each point which do not have a marsh.
Now we can solve it by considering pair of points as upper-left and lower-right to determine if a rectagular fence is possible in that rectangle but it whould take O(N^4) time.
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", mat[i] + 1);
sum[i][0] = 0;
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i][j - 1] + (mat[i][j] == 'x');
}
}
int res = 0;
for (int i = 1; i <= m; i++) for (int j = i + 1; j <= m; j++) {
int p = -1;
for (int k = 1; k <= n; k++) {
if (sum[k][j] - sum[k][i - 1] == 0) {
if (p > 0) {
res = max(res, 2 * (j - i + k - p));
} else if (p == -1) p = k;
} else if (mat[k][i] == 'x' || mat[k][j] == 'x') {
p = -1;
}
}
}
if (res > 0)
printf("%d\n", res);
else {
puts("impossible");
}
https://codepair.hackerrank.com/paper/HUAeBd01?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
O(n^4)?
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
char x;
scanf("%c", &x);
if(x == 'x')
mat[i][j] =1;
if(!mat[i][j])
left[i][j] = left[i][j - 1] + 1;
}
scanf("\n");
}
int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)if(!mat[i][j])
for(int k = j + 1; k <= m; ++k)
if(mat[i][k])
break;
else{
for(int t = i + 1; t <= n; ++t)
if(mat[t][j] || mat[t][k])
break;
else if(left[t][k] >= k - j)
ans = max(ans, 2 * (k - j + 1) + 2 * (t - i - 1));
}
https://tianrunhe.wordpress.com/2012/06/11/find-max-subsquare-whose-border-values-are-all-1/
Find max subsquare whose border values are all 1
O(n^4)
Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
Thoughts:
We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. The size of the window is the size of the subsquare. The winodw starts at different row, moving from top to bottom. When the window is fixed in a position, we chan check if this subsquare is valid or not. If so, we update the max subsquare we have found then continue.
Mr K has a rectangular land (m x n). There are marshes in the land where the fence cannot hold. Mr K wants you to find the perimeter of the largest rectangular fence that can be built on this land.
4 5
.....
.x.x.
.....
.....2 2
.x
x.
use DP to calc cumulative results of each cell, and then we use a sliding window to find max rect btw. 2 given rows.
https://www.hackerrank.com/contests/101hack/challenges/mr-k-marsh/editorialIn Problems of rectangular grids pre-calculation often help and so in this problem. Because this problem is concerned with continues points in a row/column not having any marsh it will be helpful to pre-calculate number of continues point up,down,left and right of each point which do not have a marsh.
Now we can solve it by considering pair of points as upper-left and lower-right to determine if a rectagular fence is possible in that rectangle but it whould take O(N^4) time.
rep(r1,n)
for(int r2=r1+1;r2<n;r2++)
{
vector<int> v;
int rdiff=r2-r1;
rep(j,m)
if(up[r2][j]>=rdiff)
v.push_back(j);
int l=0,r;
for(r=0;r<v.size();r++)
{
int min_left= v[r] - min( left[r1][v[r]] , left[r2][v[r]] );
while(v[l]<min_left)
l++;
if(v[r]>v[l])
max_par=max(max_par, 2*(rdiff) + 2*(v[r]-v[l]) );
}
}scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%s", mat[i] + 1);
sum[i][0] = 0;
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i][j - 1] + (mat[i][j] == 'x');
}
}
int res = 0;
for (int i = 1; i <= m; i++) for (int j = i + 1; j <= m; j++) {
int p = -1;
for (int k = 1; k <= n; k++) {
if (sum[k][j] - sum[k][i - 1] == 0) {
if (p > 0) {
res = max(res, 2 * (j - i + k - p));
} else if (p == -1) p = k;
} else if (mat[k][i] == 'x' || mat[k][j] == 'x') {
p = -1;
}
}
}
if (res > 0)
printf("%d\n", res);
else {
puts("impossible");
}
https://codepair.hackerrank.com/paper/HUAeBd01?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
O(n^4)?
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j){
char x;
scanf("%c", &x);
if(x == 'x')
mat[i][j] =1;
if(!mat[i][j])
left[i][j] = left[i][j - 1] + 1;
}
scanf("\n");
}
int ans = 0;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)if(!mat[i][j])
for(int k = j + 1; k <= m; ++k)
if(mat[i][k])
break;
else{
for(int t = i + 1; t <= n; ++t)
if(mat[t][j] || mat[t][k])
break;
else if(left[t][k] >= k - j)
ans = max(ans, 2 * (k - j + 1) + 2 * (t - i - 1));
}
https://tianrunhe.wordpress.com/2012/06/11/find-max-subsquare-whose-border-values-are-all-1/
Find max subsquare whose border values are all 1
O(n^4)
Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.
Thoughts:
We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. The size of the window is the size of the subsquare. The winodw starts at different row, moving from top to bottom. When the window is fixed in a position, we chan check if this subsquare is valid or not. If so, we update the max subsquare we have found then continue.
public static int[][] findMaxSubsquare(int[][] square) { int[][] maxSubsquare = null; int maxSize = 0; for (int col = 0; square.length - col > maxSize; ++col) { for (int row = 0; square.length - row > maxSize; ++row) { for (int size = square.length - Math.max(row, col); size > maxSize; --size) { if (isValidSubsquare(square, row, col, size)) { maxSize = size; maxSubsquare = new int[size][size]; for (int i = row; i < size + row; ++i) System.arraycopy(square[i], col, maxSubsquare[i - row], 0, size); } } } } return maxSubsquare;}private static boolean isValidSubsquare(int[][] square, int row, int col, int size) { // up and bottom border for (int j = col; j < col + size; ++j) { if (square[row][j] == 0) return false; if (square[row + size - 1][j] == 0) return false; } // left and right border for (int i = row; i < row + size; ++i) { if (square[i][col] == 0) return false; if (square[i][col + size - 1] == 0) return false; } return true;}