What a masterpiece problem! Editorial solution is also not being accepted. I am trying out this question for 7 hours


#1

const int maxn=1009;
const int maxc=3;
int l[maxc];
int rgt[maxc];
int top[maxc][maxn];
int bottom[maxc][maxn];
int mapcolor(char c)
{
if (c == ‘r’)
return 0;
else if (c == ‘g’)
return 1;
else if (c == ‘b’)
return 2;
}
double findarea(int r,int c)
{
double ans = (double)1;

// for each column
for (int i = 0; i < c; i++)

    // for each top vertex
    for (int x = 0; x < 3; x++)

        // for each bottom vertex
        for (int y = 0; y < 3; y++)
        {
            // finding the third color of
            // vertex either on rgt or l.
            int z = 3 - x - y;

            // finding area of triangle on l side of column.
            if (x != y && top[x][i] != 1000000 && bottom[y][i] != -1 && l[z] != 1000000)
            {
                ans = max(ans, ((double)1/(double)2) *
                               (bottom[y][i] - top[x][i] + 1) *
                                (i - l[z] + 1));
            }

            // finding area of triangle on rgt side of column.
            if (x != y && top[x][i] != 1000000 &&
                          bottom[y][i] != -1 &&
                          rgt[z] != -1)
            {
            //  if(x==0 && y==2)cout<<bottom[y][i]<<" "<<top[x][i]<<" "<<rgt[z]<<endl;
                ans = max(ans, ((double)1/(double)2) *
                                (bottom[y][i] - top[x][i] + 1) *
                                (rgt[z] - i + 1));
            }
        }

return ans;

}
// Precompute the vertices of top, bottom, l
// and rgt and then computing the maximum area.
double maxarea(vector& mat,int r, int c)
{
for(int i=0;i<3;i++)
{
l[i]=1000000;
rgt[i]=-1;
for(int j=0;j<c;j++)
{
top[i][j]=1000000;
bottom[i][j]=-1;
}
}

// finding the r, b, g cells for the l
// and rgt vertices.
for (int i = 0; i < r; i++)
{
    for (int j = 0; j < c; j++)
    {
        l[mapcolor(mat[i][j])] =
              min(l[mapcolor(mat[i][j])], j);
        rgt[mapcolor(mat[i][j])] =
              max(l[mapcolor(mat[i][j])], j);
    }
}
// finding set of {r, g, b} of top and
// bottom for each column.
for (int j = 0; j < c; j++)
{
    for( int i = 0; i < r; i++)
    {
        top[mapcolor(mat[i][j])][j] =
             min(top[mapcolor(mat[i][j])][j], i);
        bottom[mapcolor(mat[i][j])][j] =
             max(bottom[mapcolor(mat[i][j])][j], i);
    }
}
return findarea(r,c);

}
int Solution::solve(vector &A) {
double res=maxarea(A,A.size(),A[0].size());
return ceil(res);
}


#2

Is it the test case with output 120?


#3

yes. stupid interviewbit


#4

Yes I am also having problem as that is shown to have 120 as answer but I get 128 following the given example of area 10 which should have been 6 btw.


#5

Wrong test cases …


#6

If you guys have any doubt about testcases or soln check this out…it will surely help you guys