CHEFPAT - Editorial

It gives index of an element in arr, picked from dup array. I’ll try finding index with other approach, thanks for your time!

you can actually check. It is a stable sorting algorithm. when this is used with c++
sort STL as follows. I have even used this in my code and even in dry run it is stable.

sort(a.begin(),a.end(),sortbysec);
assuming a is vector of pairs.

I think sorting wasn’t required. Map is already ordered so it would store illness in ascending order then you could traverse the map in reverse order.

Then there must be some other reason for WA.

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

bool sortbysec(const pair<int,int> &a,
const pair<int,int> &b)
{
return (a.second > b.second);
}

int main()
{
int T;
cin>>T;
for(int i=0; i<T; i++)
{
long long int n;
cin>>n;
long long int arr1[n];
long long int arr2[n];
for(long long int i=0; i<n; i++)
{
long long int k;
cin>>k;
arr1[i] = k;
arr2[i] = i;
}
vector<pair<long long int, long long int>> vect;

    for (long long int i=0; i<n; i++) 
	    vect.push_back( make_pair(arr2[i], arr1[i]) ); 
	   
    sort(vect.begin(), vect.end(), sortbysec); 
    long long int ans[n];
    long long int c = 1;
    for (long long int i=0; i<n; i++) 
	{ 
// 		cout << vect[i].first << " "
// 			<< vect[i].second << endl; 
        ans[vect[i].first] = c;
        c++;
	} 
	for(long long int e: ans)
	    cout<<e<<" ";
    cout<<endl;
}
return 0;

}

I have used one header file now but I am getting error what’s wrong with my approach can anyone tell me?

can anyone tell me why am i getting a TLE?

for _ in range(int(input())):
n=int(input())
lst=list(map(int,input().split()))[:n]
nlst=lst.copy()
lst=sorted(lst,reverse=True)
l=[]
for i in nlst:
l.append(lst.index(i))
lst[lst.index(i)]=“a”

for i in l:
    print(i+1,end=" ")
print()
l.clear()

the indentations are correct btw

Hey CPP lovers ! those are getting WA in this may use stable_sort() on the place of sort().Because stable_sort() uses merge sort hence stable. But in normal sort () this cannot be guaranteed. You will get AC!. Stable sort are those in which we not change the order of equal elements.
My solution
Solution: 43041332 | CodeChef

2 Likes

I have used the following approach and it was accepted. Any suggestions to improve this logic are welcomed.

for i in range(int(input())):
    x = int(input())
    line = [int(i) for i in input().split()]
    line_copy = sorted(line, reverse = True)
    data = {}
    for i in range(x):
        if line_copy[i] not in data:
            data[line_copy[i]] = i+1
    for i in range(x):
        time = data[line[i]]
        data[line[i]]+= 1
        line[i] = time
    print(*line, sep = " ")

hey can anybody help me with my code please , it gives tle , how can i optimize it ??
code is here - Solution: 43044114 | CodeChef

[O(N) Solution based on C++ STL]

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ll;
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define len(a) ((int) (a).size())
#define endl “\n”
#define mod 1000000007
#define ll long long
#define ld long double
bool mycompare(pair<int,int>p1,pair<int,int>p2)
{
if(p1.first==p2.first)
return p1.second<p2.second;
else
return p1.first>p2.first;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
//code here//
ll t;
cin>>t;
while(t--)
{
    ll n;
    cin>>n;
   unordered_map<int,int> mp;
   vector<pair<int,int>> v;
    ll arr[n];
    for(ll i=0;i<n;i++)
    {
        cin>>arr[i];
        v.push_back(make_pair(arr[i],i));
    }
    sort(v.begin(), v.end(),mycompare);
    ll x=1;
    for(auto it=v.begin(); it!=v.end();it++)
    {
        int it2=(*it).second;
        mp[it2]=x;
        x++;
    }
    for(ll i=0;i<n;i++)
    {
        cout<<mp[i]<<" ";
    }
    cout<<endl;
}
return 0;

}

https://www.codechef.com/viewsolution/43033472
Can anyone please suggest changes in my code to optimize it to O(NlogN) ?

My implementation using Multimap:

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

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); 
    cout.tie(NULL);
    long long int t,n,i;
    cin>>t;
    while(t--)
    {
        cin>>n;
        multimap<long long int,int,greater<long long int> >occ;
        long long int arr[n];
        for(i=0;i<n;i++)
        {
            cin>>arr[i];
            occ.insert({arr[i],i});
        }
        i=1;
        for(auto e:occ)
        {
            arr[e.second]=i;
            i++;
        }
        for(auto e:arr)
            cout<<e<<" ";
        cout<<"\n";
    }
    return 0;
}
2 Likes

can anyone please provide me the solution with priority queue in c++

We can further optimize this in O(n) time complexity using hashing concept.
below is the code

#include <bits/stdc++.h>

using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int a[n],frq[1001],mapa[1001];
for(int i=0;i<1001;i++)
{
frq[i]=0;
mapa[i]=0;
}
for(int i=0;i<n;i++)
{
cin>>a[i];
frq[a[i]]+=1;
}
int final[n],hr=1;
for(int i=1000;i>=1;i–)
{
if(frq[i]>0)
{
mapa[i]=hr;
hr+=frq[i];
}
}
for(int i=0;i<n;i++)
{
final[i]=mapa[a[i]];
cout<<final[i]<<" “;
mapa[a[i]]++;
}
cout<<”\n";
}
return 0;
}

there is a mistake in your bool function u have not checked for the condition when a.second == b.second
bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
if(a.second>b.second){
return 1;
}
else if(a.second==b.second){
return (a.first<b.first);
}
else{
return 0;
}
}

@rp203910 mentioned it is not stable. They said there’s something like stable_sort in CPP.

I did look it up during the contest. Its documentation says it uses IntroSort(a hybrid of Heap Sort, Quick Sort and Insertion Sort). I wonder how it could have been unstable. I’m sorry for giving you the wrong direction.

ohhh!! yes, Thank You for helping it works.