Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

HackerEarth Doghouses problem solution

YASH PAL, 31 July 2024
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

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;
}
coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes