Reduce time limit of program

[Maggi Iggam]

Here is the question :-

Problem 2: What is the Rank?, (K Narayan Kumar, CMI)
This is one more story about our old friend, the Despotic King. Once every year, it was customary for the king to give audience to the rich merchants of his country in a large hall. On that day, the merchants were ushered in to meet the king one by one and after paying their respects to the king they were seated in the auditorium.
It was the job of the minister to introduce each merchant, as he arrived, to the others in the hall. He would announce his name and his wealth. However, our quirky king demanded that in addition, he should also announce the rank of the merchant among all those in the hall (at the time of his arrival) in terms of his wealth.
For example, let us suppose that the wealth of the 6 merchants who met the king (in the order in which they arrived) is given by the sequence
78 24 68 40 39 89
Then, clearly the first merchant is the richest in the hall when he enters it (since there are no others in the hall) and so his rank is 1. Since 24 < 78 the rank of the second merchant when he enters the hall is 2. The rank of the third merchant is also 2 since 24 < 68 < 78. The rank of the fourth merchant is 3 since 24 < 40 < 68 < 78, the rank of the fifth merchant is 4 since 24 < 39 < 40 < 68 < 78 and finally the rank of the sixth merchant is 1 since 24 < 39 < 40 < 68 < 78 < 89. The sequence of ranks announced by the minister would thus be:
1 2 2 3 4 1
Your task is to write a program that takes as input a sequence of distinct positive integers indicating the wealth of the merchants in the order in which they visit the king and outputs the sequence of ranks announced by the minister.
Input format
The first line contains a single integer N indicating the number of merchants. The next N lines (line 2,...,N+1) describe the wealth of these N merchants. Line i+1 contains a single positive integer indicating the wealth of the ith merchant to enter the hall.
Output format
Your output should consist of N lines. Line i should be the rank announced when the ith minister enters the hall.
Test Data:
You may assume N ≤ 45000 and that no two merchants have the same wealth. Further you may also assume that in 30% of of the inputs N ≤ 8000.
Example:
Here are the inputs and outputs corresponding to the example discussed above.
Sample Input
6
78
24
68
40
39
89
Sample Output
1
2
2
3
4
1

CPU Timelimit: 3 seconds
Memory limit: 64M

And heres the solution i programmed :-

#include <iostream>
using namespace std;
int main(){
int n,i,o,rank=1;
cin >>n;
int a_merchants[n],disp_rank[n];
for (i=0;i<n;i++) {
cin>>a_merchants[i];
for (o=0;o<=i;o++) {
if (a_merchants[o]>a_merchants[i]) rank++;
}
disp_rank[i]=rank;
rank=1;
}
for (i=0;i<n;i++) {
cout<<disp_rank[i]<<"\n";
}
}

But it is telling me that i am exceeding time limit of 3 seconds ! Can anyone Please modify my code in order to bring time limit less than 3 seconds !!! Thanks in advanced

[Stewbond]

First,

int n;
cin >>n;
int a_merchants[n];

Should not work. You cannot declare an array with a size that comes from a non-constant variable.

I would instead do int a_merchants[45000]; since you are required to support up to 45,000 inputs. An int array of this size will take up 176kB of memory, well within your memory limits.

Next, if you want to do 45,000 inputs and stay under 3 seconds, you'll need to replace the cin's with something else. When your code comes accross the cin, it "blocks" meaning that it just sits and waits for an input, wasting time and I don't think anyone could write 45,000 inputs in 3 seconds. I'd suggest reading from a file with ifstream fin("input.txt");.

[Stewbond]

I just wrote a solution to this problem out of my own interest.

I used this code to create a file with 45000 random numbers.

int main() {
	srand(time(NULL);
	ofstream fout("input.txt");
	for (int i = 0; i < 45000; i++)
		fout << rand() << endl;
}

Then in my algorithm I used:

ifstream fin("input.txt");
ofstream fout("output.txt");

instead of cin or cout. The reason for this is that writing to the console takes a certain amount of time. If I used cout my code took 10 seconds to process. If I used fout my algorithm took 2 seconds. That's a significant difference by swapping these!

I checked my time by doing this:

#include <ctime>
int main() {
    time_t StartTime = time(NULL);
/*
    Your algorithm here
*/
    cout << "Time Taken: " << time(NULL) - StartTime << " seconds" << endl;
    return 0;
}

[ne555]

Your solution is O(n^2), you need to reduce the order. (try to keep it ~1e6)
However you may scratch the time limit in some cases (specially if they considerer another languages, but not threath them different).

Think that you need an efficient way of know the position of the number, and to update that structure. I tried a trie.

In order to test the solution, use redirection

time ./a.out > output

[Maggi Iggam]

Thankyou all, i have finally got it to work !
Heres the simple solution if anybody is interested !!!


#include <iostream>
using namespace std;
int main(){
unsigned int n,i=0,r=1;
cin>>n;
unsigned int a[(n+n)],o;
do {
cin>>a[i];
for (o=0;o<=i;o++) if (a[o]>a[i]) r++;
a[(n+i)]=r;
r=1;i++;
} while(i<n);
for (i=0;i<n;i++) cout<<a[(n+i)]<<"\n";
}