TopCoder High School SRM 36 Level one - 250 pt - Vegetable Field solution

TopCoder High School SRM 36 Level one - 250 pt - Vegetable Field statement: http://community.topcoder.com/stat?c=problem_statement&pm=8059&rd=10774

TopCoder High School SRM 36 Level one - 250 pt - Vegetable Field editorial: http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=hs_srm36

TopCoder High School SRM 36 Level one - 250 pt - Vegetable Field solution:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class VegetableField {
    public: int biggestPlot(vector <string> f) {
        int a[30]={0}, cnt=0, dif=0, ans=0;
        for(int i=0; i<f.size(); i++) {
            for(int j=0; j<f[i].length(); j++) {
                for(int k=i; k<f.size(); k++) {
                    for(int l=j; l<f[i].length(); l++) {
                        for(int m=0; m<30; m++) a[m]=0;
                        dif=0, cnt=0;
                        for(int m=i; m<=k; m++) {
                            for(int n=j; n<=l; n++) {
                                if(a[f[m][n]-'A']==0) dif++;
                                else cnt++;
                                a[f[m][n]-'A']++;
                            }
                        }
                        if(dif==1) ans=max(ans, cnt+1);
                        else if(dif==2) ans=max(ans, cnt+2);
                    }
                }
            }
        }
        return ans;
    }
};

note on my solution: array a[] is set to 0. for possible rectangles array a[alphabet to int]++ is incremented. if a[alphabet to int]==0 is zero increment dif++ different alphabet. else if a[alphabet to int]>0 is bigger than zero, then we increment cnt++, count of same alphabet. and after the loop, check if dif<=2 is lesser than two, because that was what we intended to achieve. if so, ans=max(ans, cnt+1 or cnt+2) assign number of same one letter or two letters to the answer.

and here is anastasov.bg's solution: http://ideone.com/7jqj8b

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

class VegetableField {
    public: int biggestPlot(vector <string>);
};

template <class T> inline void checkmax( T &a, T b) { if(a<b) a=b; }

int cnt[256];

int VegetableField::biggestPlot(vector <string> field) {
    /*
    In this problem we are asked to find a rectangle, which is
    formed with (at most two) different characters and also have
    the biggest area. As the given plot is relatively small (20x20),
    we can just generate all possible rectangles and choose the
    biggest one.

    This bruteforce solution has time complexity of O(R^3+C^3), where
    R and C are the numbers of rows and columns respectively.
    */
    int i, j, k, l, m, n;
    int R = field.size(), C = field[0].size();
    int answer = 0, diff;
    for(int i=0; i<R; i++) for(int j=0; j<C; j++) {
        /*
        These two loops will get all the top-left possible corners
        of all rectangles.
        */
        for(int k=i; k<R; k++) for(int l=j; l<C; l++) {
            /*
            These two loops will get all the down-right possible
            corners of all rectangles.

            Now the rectangle is (i, j), (k, l), where the first
            pair is top-left corner and the other one -
            the bottom-right.
            */
            diff=0;
            memset(cnt, 0, sizeof(cnt));
            for(m=i; m<=k; ++m) for(int n=j; n<=l; ++n) {
                /*
                Counting the different number of characters is easy
                through the global array cnt[].
                */
                if(++cnt[(int)field[m][n]]==1) {
                    if(++diff>2) break;
                }
            }
            /*
            The rectangle is proper iff the number of different
            chars is at most 2. If so update if it is bigger than
            the last one.
            */
            if(diff<=2) {
                checkmax(answer, (k-i+1)*(l-j+1));
            }
        }
    }
    return answer;
}

solution 2: http://community.topcoder.com/tc?module=HSProblemSolution&cr=22686287&rd=10774&pm=8059

#include <algorithm>
#include <functional>

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <string>
#include <sstream>
#include <iostream>

#include <set>

using namespace std;

#define FORC(it,v) for( __typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it )

using namespace std;

class VegetableField {
public:
  int biggestPlot( vector <string> );
};

int cnt[256];

int VegetableField::biggestPlot( vector <string> field ) {
  
  int maxi = 0;
  
  int R = field.size();
  int C = field[0].size();
  
  for( int i = 0; i < R; ++i )
  {
    for( int j = 0; j < C; ++j )
    {
    
      
      for( int k = i; k < R; ++k )
      {
        for( int l = j; l < C; ++l )
        {
          
          set<char> dif;
          
          for( int m = i; m <= k; ++m )
          {
            for( int n = j; n <= l; ++n ) 
            {
              dif.insert( field[m][n] );
            }
          }
          
          int sz = (k-i+1)*(l-j+1);
          
          if( dif.size() <= 2 && maxi < sz ) maxi = sz;
          
        }
      }
    }
  }
  
  return maxi;
  
}

or you can peep to neal_wu's solution: http://community.topcoder.com/tc?module=HSProblemSolution&cr=22663117&rd=10774&pm=8059

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <string>
#include <iomanip>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
using namespace std;

class VegetableField
{
  public:
  
  vector <string> grid;
  int rows, cols;
  int ans;
  
  inline bool check (int r, int c, int l1, int l2)
  {
    set <char> s;
    
    for (int i = r; i < r + l1; i++)
      for (int j = c; j < c + l2; j++)
        s.insert (grid [i][j]);
    
    return (s.size () <= 2);
  }
  
  int biggestPlot (vector <string> field)
  {
    rows = field.size (), cols = field [0].length ();
    grid = field;
    ans = 0;
    
    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        for (int k = 1; k <= rows - i; k++)
          for (int l = 1; l <= cols - j; l++)
            if (check (i, j, k, l))
              ans = max (ans, k * l);
    
    return ans;
  }
};