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


HackerEarth Class representatives problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const 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;
}