PROBLEM LINK: LINK
Author: Nishit Sharma
Tester: Prerit Kumar Jha
Editorialist: Nishit Sharma
DIFFICULTY:
SIMPLE.
PREREQUISITES:
Combinatorics, Basic Maths.
PROBLEM:
There are N horses taking part in the competition with speeds of A1, A2, ..., AN respectively. It is given that all speeds are distinct. Multiple races are being conducted ,For the all 1\leq i \leq N , find the number of subsets with size ā„ 2 such that if a race were to be conducted between horses in this subset then the ith horse would finish in the top three. Since the answer might be quite large, compute it, modulo 1,000,000,007 (109+7).
EXPLANATION:
Tap to view
Since all the speeds are distinct we can easily use a map in c++ or dictionary in python to store the index corresposding to each speed. After this sort the all speeds in increasing order.
We will do all further calculations considering 0 based indexing.
For the ith horse the answer can be calculated by fixing the position of this horse. The calculations can be done as follows
- If the ith horse comes 1st in a race then all other horses will have speeds less than that of ith horse. Hence all non-empty subsets of horses having speeds less than A[i] are considered for this case. This can easily be calculated by using the formula 2^i-1.
- If the ith horse comes 2nd in a race then only 1 horse will have speed greater than A[i]. We can choose 1 horse from the n-i-1 horses with speeds greater than this horse and multiply it with all possible subsets(including empty subset) of horses having speed less than this horse.
Hence the total number of subsets will be \binom{n-i-1}{1} * 2^i - If the ith horse comes 3rd in a race then 2 horses will have speed greater than A[i]. We can choose 2 horses from the n-i-1 horses with speeds greater than this horse and multiply it with all possible subsets(including empty subset) of horses having speed less than this horse.
Hence the total number of subsets will be \binom{n-i-1}{2} * 2^i
The final answer for the ith horse will be the sum of the above three cases.
Note : Use modulo while performing all operations.
Overall Time Complexity: O((N)log(N))
CODE:
Setter's Solution(C++)
#include<bits/stdc++.h>
#define ll long long int
#define fab(a,b,i) for(int i=a;i<b;i++)
#define MOD 1000000007
#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
ll add(ll x, ll y) {ll res = x + y; return (res >= MOD ? res - MOD : res);}
ll mul(ll x, ll y) {ll res = x * y; return (res >= MOD ? res % MOD : res);}
ll power(ll x, ll y) {ll res = 1; x %= MOD; while (y) {if (y & 1)res = mul(res, x); y >>= 1; x = mul(x, x);} return res;}
using namespace std;
#define int ll
int nc2( int n)
{
if(n<2)
return 0;
return (n*(n-1))/2;
}
int32_t main()
{ quick;
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n];
map<int,int> m;
fab(0,n,i)
{cin>>a[i];
assert(m.find(a[i])==m.end() and a[i]>=1 and a[i]<=1e9);
m[a[i]]=i;
}
sort(a,a+n);
vector<int> ans(n);
fab(0,n,i)
{
int come1=power(2,i)-1;
int come2=mul(power(2,i),n-i-1);
int come3=mul(power(2,i),nc2(n-i-1));
ans[m[a[i]]]=add(come3,add(come2,come1));
}
for(auto i: ans)
{cout<<i<<" ";
assert(i<MOD and i>=0);
}
cout<<endl;
}
cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define endl '\n'
ll gcdExtended(ll a, ll b, ll *x, ll *y);
ll modInverse(ll b, ll m)
{
ll x, y;
ll g = gcdExtended(b, m, &x, &y);
if (g != 1)return -1;
return (x%m + m) % m;
}
ll modDivide(ll a, ll b, ll m)
{
a = a % m;
ll inv = modInverse(b, m);
return (inv * a) % m;
}
ll gcdExtended(ll a, ll b, ll *x, ll *y)
{
if (a == 0){
*x = 0, *y = 1;
return b;
}
ll x1, y1;
ll gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}
// CODE STARTS FROM HERE
const ll limit=1e5+1;
ll power_2[limit];
void initialize(){
power_2[0]=1;
for(ll i=1;i<1e5+2;i++){
power_2[i]=(2*power_2[i-1])%mod;
}
}
int main(){
initialize();
ll t;cin>>t;
while(t--){
ll n;cin>>n;
ll a[n],b[n];
map<ll,ll> mp;
for(ll i=0;i<n;i++){
cin>>a[i],mp[a[i]]=i;
}
sort(a,a+n,greater<ll>());
ll var = 0, ans = 0;
auto ncr = [&] (ll N,ll R){
if(R==0) var = 1;
if(R==1) var = N;
if(R==2) {
var = (N*(N-1)) % mod;
var = modDivide(var,2,mod) ;
}
};
for(ll i=0;i<n;i++){
if(i<=2){
ans = power_2[n-1];
ans = ( ans - 1 + mod ) % mod;
b[mp[a[i]]] = ans;
}
ll greater = i;
ll lesser = n-i-1;
ans = power_2[lesser];
ncr(greater,0);
ll ans1 = ( ans - var + mod ) % mod;
ncr(greater,1);
ll ans2 = ( ans * var ) % mod;
ncr(greater,2);
ll ans3 = ( ans * var ) % mod;
b[mp[a[i]]] = ( ans1%mod + ans2%mod + ans3%mod ) % mod;
}
for(ll i=0;i<n;i++)cout<<b[i]<<" ";
cout<<endl;
}
}
Python Solution
mod=(10**9)+7
T=int(input())
for _ in range(T):
N=int(input())
A=list(map(int,input().split()))
B=[[A[i],i] for i in range(N)]
B.sort()
ans=[0 for i in range(N)]
for i in range(N):
ind=B[i][1]
val=((pow(2,i,mod)-1)+((pow(2,i,mod)*(N-i-1))%mod)+(pow(2,i,mod)*((N-i-1)*(N-i-2)//2))%mod)%mod
ans[ind]=val
print(*ans)
If anything is unclear please let me know in the comments, it will help me improve.