PROBLEM LINK:
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;
}