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
CodeChef: Practical coding for everyone
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 - CodeChef: Practical coding for everyone
[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;
}
}
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.
Here is my approach:-
Please comment about its time complexity.
#include <bits/stdc++.h>
using namespace std;
#define IOS
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int32_t main()
{
IOS;
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
multimap<int, int, greater> mp;
for (int i = 0; i < n; i++)
{
int e;
cin >> e;
mp.insert({e, i});
}
map<int, multimap<int, int>> mpp;
auto i = mp.begin();
for (int a1 = 1; a1 < n + 1; a1++)
{
int a, b;
a = i->first;
b = i->second;
mpp.insert(make_pair(b, multimap<int, int>()));
mpp[b].insert(make_pair(a, a1));
i++;
}
auto itr = mpp.begin();
auto ptr = mp.begin();
for (itr; itr != mpp.end(); itr++)
{
for (ptr = itr->second.begin(); ptr != itr->second.end(); ptr++)
{
cout<<ptr->second<<" ";
}
}
cout << endl;
}
return 0;
}
Binary search? Sort in descending order, then keep searching for the closest-to-left illness level, and keep marking.
Here’s my solution using Binary Search
I am getting TLE error, idk why…?? Any suggestions??
#include<bits/stdc++.h>
using namespace std;
#define long long int;
int forMax(int arr[], int n){
int max = 0;
for(int i=0; i<n; ++i){
if(max < arr[i]){
max = arr[i];
}
}
return max;
}
int forIndex(int arr[], int n, int value){
for(int i=0; i<n; ++i){
if(arr[i] == value){
return i;
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int arr[n];
int output[n];
for(int i=0; i<n; ++i){
cin>>arr[i];
}
for(int i=0; i<n; ++i){
int max = forMax(arr, n);
int index = forIndex(arr, n, max);
arr[index] = -1;
output[index] = i+1;
}
for(auto i:output){
cout<<i<<" ";
}
cout<<endl;
}
return 0;
}
yes please tell .I did the same
I have used map and set to obtain the solution in effective manner. Below i have shared my approach.
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int T,N;
cin>>T;
while(T--){
cin>>N;
map<int,set<int>>ill_level;
int num=0;
for(int i=0;i<N;i++){
cin>>num;
ill_level[num].insert(i);
}
int ans[N];
int t=1;
for(auto itr2=ill_level.rbegin();itr2!=ill_level.rend();itr2++){
set<int>s=itr2->second;
for(auto itr=s.begin();itr!=s.end();itr++){
ans[*itr]=t;
t++;
}
}
for(int i=0;i<N;i++)
std::cout << ans[i] <<" ";
cout<<endl;
}
return 0;
}
Thanks. It worked
You might want to use Stable sort