# HackerEarth Class representatives problem solution

In this HackerEarth Class representatives, problem-solution John teaches a class of n students. Each student is assigned a unique roll number from 1 to n. He also knows the heights of each student. He needs to select a set of class representatives (a class can have any number of representatives).

A set of students are valid candidates for representatives if the following condition holds:

There does not exist a pair of students i,j such that roll[i] < roll[j] and height[i] >= height[j].
John wants to select the maximum number of students as class representatives. However, he has a new student that got enrolled whose height is x. In order to increase the number of class representatives, John assigns him a roll number i (from 1 to n + 1) randomly and then increases the roll numbers of all those students by 1 whose roll number is >= i. If the number of class representatives does not increase after this process, then he repeats the same procedure (he again assigns him a roll number from 1 to n + 1 randomly after reverting the roll numbers of all the existing students from 1 to n). Determine the expected number of times John needs to repeat this procedure in order to increase the number of class representatives.

## HackerEarth Class representatives problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll long longconst ll mod=1e9+7;ll fastexpo(ll n,ll p){    n%=mod;    return (p==0?1:fastexpo(n*n,p/2)*(p&1?n:1))%mod;}void upd(vector<ll> &st,ll clo,ll chi,ll idx,ll val,ll id){    if(clo>idx||chi<idx)return;    if(clo==chi) {st[id]=val;return;}    ll m=clo+chi>>1;    upd(st,clo,m,idx,val,id*2+1);upd(st,m+1,chi,idx,val,id*2+2);    st[id]=max(st[id*2+1],st[id*2+2]);}ll query(vector<ll> &st,ll clo,ll chi,ll lo,ll hi,ll id){    if(clo>hi||chi<lo)return 0;    if(lo<=clo&&hi>=chi) return st[id];    ll m=clo+chi>>1;    return max(query(st,clo,m,lo,hi,id*2+1),query(st,m+1,chi,lo,hi,id*2+2));}int main(){    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);    ll n,x,ht,r;cin>>n>>x;vector<ll> h(n);unordered_map<ll,ll> m;    assert(n<=5e5);assert(x<=1e7&&x>=1);    ll cntr=1;set<ll> heights;heights.insert(x);    set<ll> rols;    for(ll i=0;i<n;i++)        cin>>r>>ht,rols.insert(r),h[r-1]=ht,heights.insert(ht),assert(r>=1&&r<=n&&ht>=1&&ht<=1e7);    assert(rols.size()==n);    for(auto i:heights)m[i]=cntr++;    for(ll i=0;i<n;i++)h[i]=m[h[i]];x=m[x];    vector<ll> stb(4*n+12,0),ste(4*n+12,0),lisb(n,0),lise(n,0);    ll lis=0;    for(ll i=0;i<n;i++)    {        ll xi=h[i],mx=query(stb,0,n+2,0,xi-1,0);        lisb[i]=1+mx;upd(stb,0,n+2,xi,lisb[i],0);        lis=max(lis,lisb[i]);    }    for(ll i=n-1;i>=0;i--)    {        ll xi=h[i],mx=query(ste,0,n+2,xi+1,n+2,0);        lise[i]=1+mx;upd(ste,0,n+2,xi,lise[i],0);    }    ll por=0;    multiset<ll> les,great;les.insert(0);great.insert(0);    for(ll i=0;i<n;i++) if(h[i]>x)great.insert(lise[i]);    for(ll i=0;i<=n;i++)    {        ll m1=(*les.rbegin()+*great.rbegin())+1;        if(m1==lis+1) por++;        if(i<n&&h[i]<x) les.insert(lisb[i]);        if(i<n&&h[i]>x) great.erase(great.find(lise[i]));    }    if(por==0){cout<<-1<<endl;return 0;}    ll ans=((n+1)*fastexpo(por,mod-2))%mod;    cout<<ans<<endl;}`

### Second solution

`#include "bits/stdc++.h"using namespace std;#define fi first#define se second#define ll long long#define dbg(v) cerr<<#v<<" = "<<v<<'\n'#define vi vector<int>#define vl vector <ll>#define pii pair<int,int>#define vii vector < pii >#define mp make_pair#define db long double#define pb push_back#define all(s) s.begin(),s.end()template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}const int N = 1e6 + 5;int s[N];int t[N];int n;void upd(int i,int v) {    for (;i <= n + 1;i += i&(-i))        smax(t[i],v);}int que(int i) {    int ans = 0;    for (;i;i -= i&(-i))        smax(ans,t[i]);    return ans;}int L[N];int R[N];const int mod = 1e9 + 7;int pow(int a,int b,int mod) {    int ans = 1;    while (b) {        if (b & 1)            ans = (1ll * ans * a) % mod;        a = (1ll * a * a) % mod;        b /= 2;    }    return ans;}int main(void) {    int h;    cin>>n>>h;    vi w;    w.pb(h);    for (int i = 1;i <= n;++i) {        int a,b;        cin>>a>>b;        s[a] = b;        w.pb(b);    }    sort(all(w));    w.resize(unique(all(w)) - w.begin());    for (int i = 1;i <= n;++i)        s[i] = lower_bound(all(w),s[i]) - w.begin() + 1;    h = lower_bound(all(w),h) - w.begin() + 1;    L[0] = 0;    for (int i = 1;i <= n;++i) {        upd(s[i],que(s[i] - 1) + 1);        L[i] = que(h - 1);    }    for (int i = 1;i <= n;++i)        s[i] = n + 2 - s[i];    h = n + 2 - h;    for (int i = 1;i <= n + 1;++i)        t[i] = 0;    R[n] = 0;    for (int i = n;i >= 1;--i) {        upd(s[i],que(s[i] - 1) + 1);        R[i - 1] = que(h - 1);    }    const int LIS = que(n + 1);    int ans = 0;    for (int i = 0;i <= n;++i)        ans += L[i] + R[i] == LIS;    cout << (!ans ? -1 : (1ll * (n + 1) * pow(ans,mod - 2,mod) % mod)) << '\n';    return 0;}`