In this HackerEarth Student Arrangement problem solution, There is a classroom which has M rows of benches in it. Also, N students will arrive one-by-one and take a seat.

Every student has a preferred row number(rows are numbered 1 to M and all rows have a maximum capacity K. Now, the students come one by one starting from 1 to N and follow these rules for seating arrangements:

Every student will sit in his/her preferred row(if the row is not full).
If the preferred row is fully occupied, the student will sit in the next vacant row. (Next row for N will be 1)
If all the seats are occupied, the student will not be able to sit anywhere.
Monk wants to know the total number of students who didn't get to sit in their preferred row. (This includes the students that did not get a seat at all)


HackerEarth Student Arrangement problem solution


HackerEarth Student Arrangement problem solution.

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios::sync_with_stdio(false);
int n,m,k,i;
cin>>n>>m>>k;
int arr[n+1],cnt[m+1];
memset(cnt,0,sizeof cnt);
set <int> s;
for(i=1;i<=n;i++)
{
cin>>arr[i];
}
for(i=1;i<=m;i++)
{
s.insert(i);
}
int ans=0;
for(i=1;i<=n;i++)
{
if(s.find(arr[i])==s.end())
{
ans++;
if(!s.empty())
{
pair <set<int>:: iterator,bool> it=s.insert(arr[i]);
it.first++;
if(it.first==s.end())
{
int idx=*(s.begin());
cnt[idx]++;
if(cnt[idx]>=k)
{
s.erase(idx);
}
}
else
{
int idx=*(it.first);
cnt[idx]++;
if(cnt[idx]>=k)
{
s.erase(idx);
}
}
s.erase(arr[i]);
}
}
else
{
cnt[arr[i]]++;
if(cnt[arr[i]]>=k)
{
s.erase(arr[i]);
}
}
}
cout<<ans<<endl;
return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define all(c) (c).begin(),(c).end()
#define si(n) scanf("%d",&n)
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define PIN(n) printf("%d\n",n)
#define N 200010

int a[N];
int total[N];
int main()
{
int n,m,k;
si(n),si(m),si(k);
REP(i,0,n)
si(a[i]);
int ans = 0;
set<int> s;
REP(i,1,m+1)
s.insert(i);
REP(i,0,n)
{
if(s.empty())
{
ans+=(n-i);
break;
}
auto it = s.lower_bound(a[i]);
if(it == s.end())
it = s.begin();
if(*it != a[i])
ans++;
total[*it]++;
if(total[*it]==k)
s.erase(it);
}
PIN(ans);
return 0;
}