 # BIT2A-Editorial

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

Cakewalk

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];
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,b;
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

1 Like

the most easiest O(N) solution without using stl

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

#include
using namespace std;

int main() {
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;
``````

}