Hackerrank Ema's Supercomputer Solution
.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Ema built a quantum computer! Help her test its capabilities by solving the problem below.
Given a grid of size , each cell in the grid is either or .
A valid plus is defined here as the crossing of two segments (horizontal and vertical) of equal lengths. These lengths must be odd, and the middle cell of its horizontal segment must cross the middle cell of its vertical segment.
In the diagram below, the blue pluses are valid and the orange ones are not valid.
Find the two largest valid pluses that can be drawn on cells in the grid, and return an integer denoting the maximum product of their areas. In the above diagrams, our largest pluses have areas of and . The product of their areas is .
Note: The two pluses cannot overlap, and the product of their areas should be maximal.
Function Description
Complete the twoPluses function in the editor below. It should return an integer that represents the area of the two largest pluses.
twoPluses has the following parameter(s):
- grid: an array of strings where each string represents a row and each character of the string represents a column of that row
Input Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
The first line contains two space-separated integers, and .
Each of the next lines contains a string of characters where each character is either G () or B (). These strings represent the rows of the grid. If the character in the line is G, then is a cell. Otherwise it's a cell.
Constraints.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Output Format.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Find pluses that can be drawn on cells of the grid, and return an integer denoting the maximum product of their areas.
Sample Input 0
5 6
GGGGGG
GBBBGB
GGGGGG
GGBBGB
GGGGGG
Sample Output 0
5
Sample Input 1
6 6
BGBBGB
GGGGGG
BGBBGB
GGGGGG
BGBBGB
BGBBGB
Sample Output 1
25
Explanation.MathJax_SVG_Display {text-align: center; margin: 1em 0em; position: relative; display: block!important; text-indent: 0; max-width: none; max-height: none; min-width: 0; min-height: 0; width: 100%} .MathJax_SVG .MJX-monospace {font-family: monospace} .MathJax_SVG .MJX-sans-serif {font-family: sans-serif} .MathJax_SVG {display: inline; font-style: normal; font-weight: normal; line-height: normal; font-size: 100%; font-size-adjust: none; text-indent: 0; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0; min-height: 0; border: 0; padding: 0; margin: 0} .MathJax_SVG * {transition: none; -webkit-transition: none; -moz-transition: none; -ms-transition: none; -o-transition: none} .mjx-svg-href {fill: blue; stroke: blue} .MathJax_SVG_LineBox {display: table!important} .MathJax_SVG_LineBox span {display: table-cell!important; width: 10000em!important; min-width: 0; max-width: none; padding: 0; border: 0; margin: 0}
Here are two possible solutions for Sample 0 (left) and Sample 1 (right):
Explanation Key:
- Green: cell
- Red: cell
- Blue: possible .
For the explanation below, we will refer to a plus of length as .
Sample 0
There is enough good space to color one plus and one plus. , and . The product of their areas is .
Sample 1
There is enough good space to color two pluses. . The product of the areas of our two pluses is .
Solution in java8
Approach 1.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the twoPluses function below.
static int twoPluses(String[] grid) {
int len1=grid.length;
int len2=grid[0].length();
int k=0;
int u=0;
char arr[][]=new char[len1][len2];
int max1=1;
int max2=Integer.MIN_VALUE;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
arr[i][j]=grid[i].charAt(j);
}
}
for(int i=1;i<len1-1;i++)
{
//int len2=grid[i].length;
for(int j=1;j<len2-1;j++)
{
int m=1;
int res=0;
while( i-m >=0 && i+m<len1 && j-m >=0 && j+m < len2 && arr[i-m][j]=='G' && arr[i][j-m]=='G'&& arr[i][j+m]=='G' && arr[i+m][j]=='G')
{
arr[i][j]='V';
arr[i-m][j]='V';
arr[i+m][j]='V';
arr[i][j-m]='V';
arr[i][j+m]='V';
res=res+4;
m=m+1;
}
res=res+1;
//System.out.println("."+)
System.out.println("i: "+i+"j: "+j+"res: "+res);
// int x =Math.max(Math.max(max1,max2),res);
k=Math.max(Math.max(max1,max2),res);
if(k==max1)
{
u=Math.max(max2,res);
}
if(k==max2)
{
u=Math.max(max1,res);
}
if(k==res)
{
u=Math.max(max2,max1);
}
max1=k;
max2=u;
}
}
System.out.println("k "+k+"u "+u);
return max1*max2;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
String[] grid = new String[n];
for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}
int result = twoPluses(grid);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Approach 2.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the twoPluses function below.
static int twoPluses(String[] grid) {
char a[][]=new char[grid.length][grid[0].length()];
for(int i=0;i<grid.length;i++){
a[i] = grid[i].toCharArray();
}
int min = 1,max = 1,count=1,x=0;
for(int i=1;i<grid.length-1;i++){
for(int j=1;j<grid[0].length()-1;j++){
if(a[i][j]=='G' && a[i-1][j]=='G' && a[i+1][j]=='G' && a[i][j-1]=='G' && a[i][j+1]=='G'){
int left = j-1;
int top = i-1;
int right = j+1;
int bottom = i+1;
while(top>=0 && bottom<a.length && left>=0 && right <a[0].length && a[top][j]=='G' && a[bottom][j]=='G' && a[i][left]=='G' && a[i][right]=='G')
{
a[top][j]='0';
a[bottom][j]='0';
a[i][left]='0';
a[i][right]='0';
count+=4;
top--;
bottom++;
left--;
right++;
}
if(count>max){
min=max;
max=count;
}else if(count>min){
min=count;
}
count=1;
}
}
}
return min*max;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
String[] grid = new String[n];
for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}
int result = twoPluses(grid);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Approach 3.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the twoPluses function below.
static int twoPluses(String[] grid) {
int n=grid.length;
int m=grid[0].length();
int cnt=0;
int area=1;
int cntG=0;
for(int i=0;i<n;i++)
{
char ch[]=grid[i].toCharArray();
for(int j=0;j<m;j++)
{
if(ch[j]=='G')
{
cntG++;
int min=Math.min(n-i-1,m-j-1);
int k=j+1;
int l=j-1;
int length=0;
while(k<m && k<=min+j && l>=0 && l>=j-min)
{
if(ch[k]=='G' && ch[l]=='G')
{
length++;
}
else
break;
k++;
l--;
}
k=i+1;
l=i-1;
int height=0;
while(k<n && k<=min+i && l>=0 && l>=i-min)
{
if(grid[k].charAt(j)=='G' && grid[l].charAt(j)=='G')
{
height++;
}
else
break;
k++;
l--;
}
if(length==height && cnt<2 && length!=0)
{
cnt++;
area*=2*(length+height)+1;
}
System.out.println("i "+i+" j "+j+" length "+length+" height "+height+" cnt "+cnt+" area "+area);
}
}
}
if(cnt==1)
area*=1;
return area;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
int n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
String[] grid = new String[n];
for (int i = 0; i < n; i++) {
String gridItem = scanner.nextLine();
grid[i] = gridItem;
}
int result = twoPluses(grid);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Solution in python3
Approach 1.
Approach 2.
Approach 3.
def twoPluses(ri, c, grid):
# padding the cell
tem = []
tem.append(["O"] * (ri + 2))
for x in grid:
tem.append(["O"] + list(x) + ["O"])
tem.append(["O"] * (ri + 2))
grid = tem
# print(grid)
ans=0
for e in range(1, ri + 1):
for v in range(1, c + 1):
r = 0
# check adjacent 4 cells of [e][v] when r >0
while grid[e + r][v] == "G" and grid[e - r][v] == "G" and grid[e][v + r] == "G" and grid[e][v - r] == "G":
grid[e + r][v] =grid[e - r][v] =grid[e][v + r] =grid[e][v - r] = "g"#to avoid overlapping of 2 pluses at that instance
for E in range(1, ri + 1):#2nd plus
for V in range(1, c + 1):
R = 0
# check adjacent 4 cells of [e][v] when r >0
while grid[E + R][V] == "G" and grid[E - R][V] == "G" and grid[E][V + R] == "G" and grid[E][
V - R] == "G":
ans=max(ans,(4*r +1)*(4*R +1))
R+=1
r+=1
#revert back to "G" for each "g"
r=0
while grid[e + r][v] == "g" and grid[e - r][v] == "g" and grid[e][v + r] == "g" and grid[e][v - r] == "g":
grid[e + r][v] = grid[e - r][v] = grid[e][v + r] = grid[e][v - r] = "G"
r+=1
return ans
if __name__ == '__main__':
nm = input().split()
n = int(nm[0])
m = int(nm[1])
grid = []
for _ in range(n):
grid_item = input()
grid.append(grid_item)
result = twoPluses(n, m, grid)
print(result)
Solution in cpp
Approach 1.
#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
int area(int l) { return 4*l+1; }
int value(int y, int x, int l1, int l2) {
if (y > x) swap(y, x);
int ans = 0;
if (y == 0) {
repeat (t,x) {
ans = max(ans, area(min(t,l1)) * area(min(x-t-1,l2)));
}
} else {
repeat (t,l1+1) {
int u =
t < y ? l2 :
t < x ? min(x-1, l2) :
min(y-1, l2);
ans = max(ans, area(t) * area(u));
}
}
return ans;
}
int main() {
int h, w; cin >> h >> w;
vector<vector<bool> > is_good(h, vector<bool>(w));
repeat (y,h) repeat (x,w) {
char c; cin >> c;
is_good[y][x] = c == 'G';
}
auto is_on_field = [=](int y, int x) { return 0 <= y and y < h and 0 <= x and x < w; };
vector<vector<int> > l(h, vector<int>(w)); // possible length of 4 bars
repeat (y,h) repeat (x,w) {
while (true) {
bool valid = true;
repeat (i,4) {
int ny = y + l[y][x] * dy[i];
int nx = x + l[y][x] * dx[i];
if (not is_on_field(ny, nx) or not is_good[ny][nx]) {
valid = false;
break;
}
}
if (not valid) break;
++ l[y][x];
}
}
int ans = 0;
repeat (y1,h) repeat (x1,w) if (l[y1][x1]) {
repeat (y2,h) repeat (x2,w) if (l[y2][x2]) {
if (y1 != y2 or x1 != x2) {
ans = max(ans, value(abs(y1-y2), abs(x1-x2), l[y1][x1]-1, l[y2][x2]-1));
}
}
}
cout << ans << endl;
return 0;
}
Approach 2.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<string> G;
bool nextLevelValid(int x, int y, int l) {
if (x + l >= n || x - l < 0 || y + l >= m || y - l < 0) {
return false;
}
if (G[x + l][y] == 'B' || G[x - l][y] == 'B' || G[x][y + l] == 'B' ||
G[x][y - l] == 'B') {
return false;
}
return true;
}
bool compare(vector<int> a, vector<int> b) { return a[2] > b[2]; }
bool validCrosses(vector<int> a, vector<int> b) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
G[i][j] = 'G';
}
}
for (int i = 0; i < a[2]; ++i) {
G[a[0] + i][a[1]] = 'B';
G[a[0] - i][a[1]] = 'B';
G[a[0]][a[1] + i] = 'B';
G[a[0]][a[1] - i] = 'B';
}
for (int i = 0; i < b[2]; ++i) {
if (G[b[0] + i][b[1]] == 'B' || G[b[0] - i][b[1]] == 'B' ||
G[b[0]][b[1] + i] == 'B' || G[b[0]][b[1] - i] == 'B') {
return false;
}
}
return true;
}
int main() {
cin >> n >> m;
G = vector<string>(n);
vector<vector<int>> A(n, vector<int>(m, 0));
vector<vector<int>> C;
for (int i = 0; i < n; ++i) {
cin >> G[i];
}
// cout << "\n\n";
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (G[i][j] == 'G') {
int level = 1;
while (nextLevelValid(i, j, level)) {
++level;
}
A[i][j] = level;
// cout << level << " ";
C.push_back({i, j, level});
} else {
// cout << "0 ";
}
}
// cout << "\n";
}
// cout << "\n\n";
sort(C.begin(), C.end(), compare);
int max = 0;
for (int i = 0; i < C.size() - 1; ++i) {
for (int j = i + 1; j < C.size(); ++j) {
for (int l1 = 1; l1 <= C[i][2]; ++l1) {
for (int l2 = 1; l2 <= C[j][2]; ++l2) {
vector<int> C1 = C[i], C2 = C[j];
C1[2] = l1, C2[2] = l2;
if (validCrosses(C1, C2)) {
int loc = (C1[2] * 4 - 3) * (C2[2] * 4 - 3);
if (loc > max) {
max = loc;
}
}
}
}
}
}
cout << max << "\n";
return 0;
}Approach 3.
#include <bits/stdc++.h>
using namespace std;
vector<string> split_string(string);
// Complete the twoPluses function below.
int onePluse(vector<string> grid)
{
int m = 0;
for(int i=0;i<grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 'B') continue;
int k = 0;
while(i-k>=0 && j-k >=0 && i+k < grid.size() && j +k < grid[0].size() && grid[i-k][j] == 'G' && grid[i+k][j] == 'G' && grid[i][j-k] == 'G' && grid[i][j+k] == 'G')
{
k++;
}
if(4*k-3 > m) m = 4*k-3;
}
}
return m;
}
int twoPluses(vector<string> grid) {
int m = 0;
for(int i=0;i<grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 'B') continue;
vector<string> grid2(grid);
int k = 0;
while(i-k>=0 && j-k >=0 && i+k < grid.size() && j +k < grid[0].size() &&
grid[i-k][j] == 'G' && grid[i+k][j] == 'G' && grid[i][j-k] == 'G' && grid[i][j+k] == 'G')
{
grid2[i-k][j] = 'B';
grid2[i+k][j] = 'B';
grid2[i][j-k] = 'B';
grid2[i][j+k] = 'B';
k++;
int temp = 4*k-3;
int temp2 = onePluse(grid2);
if(temp * temp2 > m) m = temp *temp2;
}
}
}
return m;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string nm_temp;
getline(cin, nm_temp);
vector<string> nm = split_string(nm_temp);
int n = stoi(nm[0]);
int m = stoi(nm[1]);
vector<string> grid(n);
for (int i = 0; i < n; i++) {
string grid_item;
getline(cin, grid_item);
grid[i] = grid_item;
}
int result = twoPluses(grid);
fout << result << "\n";
fout.close();
return 0;
}
vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});
input_string.erase(new_end, input_string.end());
while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}
vector<string> splits;
char delimiter = ' ';
size_t i = 0;
size_t pos = input_string.find(delimiter);
while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));
i = pos + 1;
pos = input_string.find(delimiter, i);
}
splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
return splits;
}
