Can anyone help to optimize my code,i am gettinf TLE

1

I am getting TLE ,please help me to optimize it.
problem link = CodeChef: Practical coding for everyone

int main() {

ios_base::sync_with_stdio(0);

cin.tie(0);

int t;
cin>>t;
for(int i=0;i<t;i++){
int n;
cin>>n;
int A[n],copyA[n];
for(int i=0;i<n;i++){
cin>>A[i];
copyA[i]=A[i];

}
sort(A,A+n);
reverse(A, A+n); 
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(copyA[i]==A[j]){
  cout<<j+1<<" ";
  A[j]=0;
  break;
}    
}
}
cout<<"\n";

}

return 0;

}

2

Can you please attach your problem statement link as well?

1 Like
3

I will work if the value of n<=10^4 time complexity of you program is n^2 so if the que constrain is n<=10^6 then for code need better approach example - O(nlogn)

4
5

As the input constraints are quite tight for an O(n^2) approach (as you did).
Some approach thought process:

  1. Can use multimap and then sorting according to keys (i.e. using a greater<int> (), as it is a multimap and ordering matters and also value of map will be indexes) and then incrementing their count starting from 1. // not the best approach i would say but would work
  2. DP (maintaining counts position wise insertion) // not so sure about this
  3. If other contributors have their approaches, they can add as well.
6

Hi @abhishek_645 Your approach is correct.
\mathcal{O}(n^2) approach won’t work here, The desired time complexity is \mathcal{O}(nlogn)

We can use a container called Map and custom sorting function to reduce time complexity in this case,
We need to sort them correct. If two elements have same value we need to check which element is coming earlier, So we can see we also need to keep track of indexes and elements so we can just store them in form of index value pairs and sort them.
We also copy the original array in a dummy array as you did to preserve the order.

pair<patient_illness,index_in_queue>p

To sort we will need to write a custom function like this.

bool comp(pair<int, int>&a, pair<int, int>&b)
{
	if (a.first == b.first)
	{
		return a.second < b.second;
	}
	return a.first > b.first;
}

This will give us the array in the form we desire and then we can
assign each of them an hour according to the condition. We can use map to do so

map[pair<patient_illness , index_in_queue>] = time

And we can use the original array and print the time assigned to the current patient using the map.

You can check my submission using the same method here: Sameer’s Submission

2 Likes
7

As @sameer_bamanha said, this solution requires O(nlogn) complexity. This is another way of solving the question using reverse indexing.

1 Like
8

thanks @sameer_bamanha ,you are right.