RRUN- Editorial

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

  1. 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.
  2. 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
  3. 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.

4 Likes

I did exactly what the editorial said. Could anyone help me by telling what is wrong with my solution? Thanks.

My code: https://www.codechef.com/viewsolution/39310618

The error which Iā€™m getting is WA (Wrong Answer).

Edit: I found that there is something wrong with my power(n) function but I am unable to exactly find what it is.

overflow .

check my code : ā€œhttps://www.codechef.com/viewsolution/39312555ā€

2 Likes

very nice explanation

please explain this line . i am unable to get this.

It has nothing to do with the logic of the problem. It is only to check that all values are distinct and are between 1 and 10^9.

the first part of map stores speed and second part their index before sorting. Am i right ?

Yes you are right.

                    ans[m[a[i]]]=add(come3,add(come2,come1));

m[a[i]] = i
so it is ans [i]
is it correct ?