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 - CodeChef: Practical coding for everyone

1 Like

the most easiest O(N) solution without using stl

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

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n,i;
cin>>n;
long long int a[n];
for(i=0; i<n; i++)
{
cin>>a[i];

    }
    for(i=0; i<n; i++)
    {
        if(a[i]<a[i+1])
        {
            cout<<n-i-1<<" ";
        }
        else
        {
            cout<<0<<" ";
        }
    }
    cout<<endl;
    
}
return 0;

}

anyone can plz tell me what is the mistake in my code …its partially incorrect

#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;cin>>t;
while(t–){
int n;cin>>n;
int arr[n];

    for(int i=0 ;i<n ; i++){
        cin>>arr[i];
        }
        for(int i=0 ; i<n ; i++){
            int count = 0;
            for(int j=1 ; j<n ; j++){
            if(arr[i]<arr[j])
            count++;
        }
        cout<<count<<" ";
    }
    cout<<endl;
}
return 0;

}

formula for finding each value is
a[i] = max_position - no_duplicates_of_a[i] - count_of_numbers_less_than_a[i].
finding no of duplicates for each element and position of max element
unordered_map<int,int> hash;
** for(int i=0;i<n;i++){**
** cin>>a[i];**
** hash[a[i]]++;**
** if(a[max]<=a[i])**
** max = i;**
** }**
applying the given formula
int count = 0;
** for(int i=0;i<n;i++){**
** if(i!=0 && a[i]>a[i-1])**
** count+=hash[a[i-1]];**
** cout<<max+1-hash[a[i]]-count<<" ";**
** }**