Fixing the editorial solution for Maximum Area of Triangle!


#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<string>& 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<string> &A) {
    if(A[0]==A[1] && A[1]==A[2])
        return 0;
    double res=maxarea(A,A.size(),A[0].size());
    return ceil(res);
}


#2

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


#3

Thanks @bugs_bunny , guys just paste his solution , code is fixed acc to test cases and it works.