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