HackerEarth Doghouses problem solution

In this HackerEarth Doghouses problem solution As you probably know, cats usually fight with dogs.

There are N doghouses in a backyard. For simplicity, we consider the backyard as a plane, and the doghouses as points on the plane. All doghouses are numbered from 1 to N. The i-th doghouse is located at point (i, Y[i]). (Note that this means that there are no two doghouses with the same x-coordinate.)

Cats are about to build some rectangular fence, parallel to the axis. If some doghouse is located at the perimeter of the fence, it should be removed. Your task it to find the maximum possible number of doghouses that may be removed after choosing arbitrary fence sizes and location. Please note that the area covered by the fence may be equal to 0.

HackerEarth Doghouses problem solution.

#include<bits/stdc++.h>
const int N = 1002;
 
using namespace std;
 
vector<int> ent[N];
int n;
int y[N];
int ans;
 
int main(){
    
    cin>>n;
    
    for (int i=1;i<=n;i++)
    {
        cin>>y[i];
        ent[y[i]].push_back(i);
    }
    
    for (int dwn=0;dwn<=1000;dwn++)
    {
        int lmost,rmost;
        lmost=1e9;
        rmost=-1e9;
        for (int up=dwn;up<=1000;up++)
        {
            if (up==dwn)
            {
                ans=max(ans,(int)ent[up].size());
            }
            if (up!=dwn)
            {
                int sz=ent[up].size()+ent[dwn].size();
                ans=max(ans,sz);
            }
            if(lmost<=rmost)
            {
                int upr=upper_bound(ent[up].begin(),ent[up].end(),rmost)-lower_bound(ent[up].begin(),ent[up].end(),lmost);
                int lwr=upper_bound(ent[dwn].begin(),ent[dwn].end(),rmost)-lower_bound(ent[dwn].begin(),ent[dwn].end(),lmost);
                
                if (lmost!=rmost)
                    upr+=2;
                else
                    upr+=1;
                
                upr+=lwr;
                ans=max(ans,upr);
            }
            
            if (lmost<=rmost)
            {
                int upr=ent[up].end()-lower_bound(ent[up].begin(),ent[up].end(),lmost);
                int lwr=ent[dwn].end()-lower_bound(ent[dwn].begin(),ent[dwn].end(),lmost);
                ans=max(ans,upr+lwr+1);
                
                upr=upper_bound(ent[up].begin(),ent[up].end(),rmost)-ent[up].begin();
                lwr=upper_bound(ent[dwn].begin(),ent[dwn].end(),rmost)-ent[dwn].begin();
                ans=max(ans,upr+lwr+1);
            }
            
            if (ent[up].size()>0&&up!=dwn)
            {
                lmost=min(lmost,ent[up][0]);
                rmost=max(rmost,ent[up].back());
            }
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}

HackerEarth Doghouses problem solution.

Leave a Reply