Light OJ: 1424 – New Land

0

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1424

Solution Idea: I think this problem can be solved with a 2D Segment Tree. But here I use the histogram technique to solve this problem. You can try Spoj – HISTOGRA – Largest Rectangle in a Histogram and Light OJ – 1083 – Histogram . Both are same problem on different website. This problems can be using a niche technique called histogram which can be implemented using a stack. the algorithm determine the index of the bar before the current bar which is smaller than the current bar also determine the index of the bar after the current bar which is smaller than the current bar. Here the function func is the answer of the above two problem.

In this problem for each row we consider a histogram from current row and the rows which are above the current row with continuous 0. Then determine the maximum answer.


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

#define mx 2002

char grid[mx][mx];

int dp[mx][mx];

int func(int ara[], int n)
{
    int left[mx];

    stack<int>st;

    for(int i=0; i<n; i++)
    {
        while(!st.empty() && ara[st.top()]>=ara[i]) st.pop();
        left[i]=(st.empty()?-1:st.top());
        st.push(i);
    }

    while(!st.empty()) st.pop();

    int ret=0;
    int right;
    for(int i=n-1; i>=0; i--)
    {
        while(!st.empty() && ara[st.top()]>=ara[i]) st.pop();
        right=(st.empty()?n:st.top());
        ret=max((right-left[i]-1)*ara[i],ret);
        st.push(i);
    }
    return ret;
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);

    int t;
    sf(t);
    TEST_CASE(t)
    {
        int n,m;
        sff(n,m);
        getchar();
        for(int i=0; i<n; i++)
            sc("%s",grid[i]);

        for(int j=0; j<m; j++)
        {
            dp[0][j]=(grid[0][j]=='0')?1:0;
        }

        int ans=func(dp[0],m);

        for(int i=1; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                dp[i][j]=dp[i-1][j]+((grid[i][j]=='0')?1:-dp[i-1][j]);
            }
            ans=max(ans,func(dp[i],m));
        }
        PRINT_CASE;
        pf("%d\n",ans);

    }


    return 0;
}

SPOJ : HISTOGRA – Largest Rectangle in a Histogram

0

Problem Link : http://www.spoj.com/problems/HISTOGRA/


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             100005
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

ll ara[MAX];

ll hisogram(int n)
{
    stack<int>st;
    int i=0;
    ll ans=0;
    while(i<n)
    {
        if(st.empty() || ara[st.top()]<=ara[i])
        {
            st.push(i);
            i++;
        }
        else
        {
            int top=st.top();
            st.pop();
            ll area= ara[top]*(st.empty()?i:i-st.top()-1);
            if(area>ans)
                ans=area;
        }
    }

    while(!st.empty())
    {
        int top=st.top();
        st.pop();
        ll area= ara[top]*(st.empty()?i:i-st.top()-1);
        ans=max(ans,area);
    }
    return ans;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int n;
    while(sf(n) && n)
    {
        loop(i,n) sfl(ara[i]);
        cout<<hisogram(n)<<endl;
    }
    return 0;
}

Light OJ 1083 – Histogram

0

/*
Link: http://www.lightoj.com/volume_showproblem.php?problem=1083
*/

#include <bits/stdc++.h>

#define pii pair <int,int>
#define sc scanf
#define pf printf
#define Pi 2*acos(0.0)
#define ms(a,b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define oo 1<<29
#define dd double
#define ll long long
#define EPS 10E-10
#define ff first
#define ss second
#define MAX 10000
#define SZ(a) (int)a.size()
#define getint(a) scanf("%d",&a)
#define loop(i,n) for(int i=0;i<n;i++)
#define TEST_CASE(t) for(int z=1;z<=t;z++)
#define PRINT_CASE printf("Case %d: ",z)
#define all(a) a.begin(),a.end()
#define intlim 2147483648
#define inf 1000000
#define rtintlim 46340
#define llim 9223372036854775808
#define rtllim 3037000499
#define ull unsigned long long
#define I int

using namespace std;
int ara[30050];
int n;
ll histogram()
{
    stack<int>st;
    ll ans=0;
    int i=0;
    while(i<n)
    {
        if(st.empty() || ara[st.top()]<=ara[i])
            st.push(i++);
        else
        {
            int top=st.top();
            st.pop();
            ll top_area=ara[top]*(st.empty()?i:i-st.top()-1);
            ans=max(ans,top_area);
        }
    }
    while(!st.empty())
    {
        int top=st.top();
        st.pop();
        ll top_area=ara[top]*(st.empty()?i:i-st.top()-1);
        ans=max(ans,top_area);
    }
    return ans;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    getint(t);
    TEST_CASE(t)
    {

        getint(n);
        loop(i,n)
        sc("%d",&ara[i]);
        PRINT_CASE;
        pf("%lld\n",histogram());
    }
    return 0;
}