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 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;
}

coding problems