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 Seating Arrangement problem solution

YASH PAL, 31 July 2024
In this HackerEarth Seating Arrangement problem solution, There are N chairs arranged in a row. K people come in a line and start occupying the chairs. Each person wants to be as far as possible from every other person. So, every person arriving looks for the largest empty continuous sequence of unoccupied chairs and occupies the middle position. They have a preference indicating whether they would choose the left or the right chair if there are two chairs at the middle to chose from (else the preference does not matter since there is only 1 chair at the center). If there are multiple largest empty sequences, then the person chooses the sequence which appears first from the left side. You are asked to answer Q queries. Determine which person has occupied the queried position.
HackerEarth Seating Arrangement problem solution

HackerEarth Seating Arrangement problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(x) scanf("%d", &x)
#define sc(x) scanf("%c", &x)
#define sl(x) scanf("%lld", &x)
#define pl(x) printf("%lldn", x)
#define pi(x) printf("%dn", x)
#define gu getchar_unlocked
#define pu putchar_unlocked
#define setbits __builtin_popcountll
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define speed ios::sync_with_stdio(false)

priority_queue < pair < ll, ll > > q;
map < ll, int > m;
map < ll, int > :: iterator it;

int main(){
ll n;
sl(n);
int k, i;
si(k);
string s;
cin>>s;
q.push(mp(n, (ll)-1));
for(i = 1; i <= k; i++){
pair < ll, ll > P = q.top();
q.pop();
if(P.first % 2 == 1){
ll start = -P.second;
ll end = start + P.first - 1;
ll pos = (start + end) / 2;
m[pos] = i;
ll size1 = pos - start;
ll size2 = end - pos;
q.push(mp(size1, -start));
q.push(mp(size2, -(pos + 1)));
}
else{
ll start = -P.second;
ll end = start + P.first - 1;
ll pos = (start + end) / 2;
if(s[i - 1] == 'R'){
pos++;
}
m[pos] = i;
ll size1 = pos - start;
ll size2 = end - pos;
q.push(mp(size1, -start));
q.push(mp(size2, -(pos + 1)));
}
}
int q;
si(q);
while(q--){
ll pos;
sl(pos);
if(m.find(pos) != m.end()){
pi(m[pos]);
}
else{
pi(-1);
}
}
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
map<LL,LL> ans;
priority_queue<pair<LL , pair<LL , LL> > > pq;
int main()
{
ios_base::sync_with_stdio(0);
LL n , k, q;
string s;
cin >> n >> k;
cin >> s;
s = " " + s;

pq.push(make_pair(n , make_pair(-1 , -n)));
int cur = 0;
while(k > 0)
{
++cur;
pair<LL , pair<LL , LL> > tp = pq.top();
pq.pop();
LL sz = tp.first;
LL l = tp.second.first * (-1LL);
LL r = tp.second.second * (-1LL);
LL mid = 0;
if(sz % 2)
{
mid = (l + r) / 2;
}
else
{
mid = (l + r) / 2;
if(s[cur] == 'R')
++mid;
}
ans[mid] = cur;
if(mid > l)
{
pq.push(make_pair(mid - l , make_pair(-l , -(mid - 1))));
}
if(mid < r)
{
pq.push(make_pair(r - mid , make_pair(-(mid + 1) , -r)));
}
--k;
}
cin >> q;
while(q--)
{
LL idx;
cin >> idx;
if(ans.find(idx) == ans.end())
cout << -1 << endl;
else
cout << ans[idx] << endl;
}

}
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