BIT2A-Editorial

PROBLEM LINK:

Practice
Contest

Author: Shweta Gurnani
Tester: Jatin Nagpal
Editorialist: Shweta Gurnani

DIFFICULTY:

Cakewalk

PREREQUISITES:

Brute Force

PROBLEM:

You are given a sorted list A of size N.You have to make a new list B such that B[i] is equal to the number of elements strictly greater than A[i] in the list A.

EXPLANATION:

Method 1(Brute Force):

Make a counter array B.Traverse the array and for each A[i] again traverse the array from (i+1) to n and compare element at that location with A[i]. If element at that location is strictly greater than A[i] then B[i]++. Display the array B.

Time Complexity:O(T * N * N)

Method 2(Using C++ STL):

This is quiet a simple problem. Make a frequency map(STL) in which key of map represents the element of array and and value represents its frequency in the array(number of times it is occuring in list A). Let B is the new list to be displayed.

Now traverse the list A.

Case 1: i=0(the first element of array) then B[i]=n-(frequency of A[i]).

Case 2:1<=i<n if(A[i]=A[i-1]) then B[i]=B[i-1] (if two elements are equal then the number of elements strictly greater than them will also be equal ) otherwise B[i]=B[i-1]-(frequency of A[i]).

Time Complexity:O(T * N * log N)

SOLUTIONS:

Setter
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll t;
    cin>>t;
   assert(1<=t && t<=100);
    while(t--)
    {
        ll n;
        cin>>n;
        assert(1<=n && n<=100);
        ll A[n];
        ll c=0;
        for(ll i=0;i<n;i++)
        {
        cin>>A[i];
        assert(1<=A[i] && A[i]<=1000000);
        
        }
        for(ll i=1;i<n;i++)
        {
            if(A[i]==A[i-1])
            c++;
            else
            break;
        }
   

            map<ll,ll>mp;
            for(ll i=0;i<n;i++)
            {
            mp[A[i]]++; 
            }
            ll k=n;
            ll ans=k-mp[A[0]];
            cout<<ans<<" ";
            for(ll i=1;i<n;i++)
            {
                if(A[i]==A[i-1])
                cout<<ans<<" ";
                else
                {
                    ans=ans-mp[A[i]];
                    cout<<ans<<" ";
                }
            }
        }
        
        cout<<"\n";
    
    
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define f(i,x,n) for(int i=x;i<n;i++)
int n,a[105],b[105];
int32_t main()
{
 ios_base::sync_with_stdio(false);
   cin.tie(NULL);
int t;
cin>>t;
while(t--)
  {
           cin>>n;
     f(i,0,n)
                    cin>>a[i];
          f(i,0,n)
            {
                   b[i]=0;
             f(j,i+1,n)
                          if(a[j]>a[i])
                               b[i]++;
             cout<<b[i]<<" ";
            }
           cout<<'\n';
 }
   
    return 0;
}

Time Complexity: O(T*N)

https://www.codechef.com/viewsolution/26687310

O(N) solution - https://www.codechef.com/viewsolution/26777608