Improve run-time of C++ program

[paulrishav93]

Hello Everyone,

I have recently started programming in C++ and also started coding on Sphere Online Judge.
However, my solution got rejected as it exceeded the time limit.
Please have a look at my code and tell me what I should do to improve the running time.

#include<iostream>
using namespace std;

int main()
{
    int t,n,i,j,val,k;
    int *p,*a;
    cin>>t;
    
    while(t--)
    {
           cin>>n;
           
           p=new int[n];
           a=new int[n];
           
           for(i=0;i<n;i++)
           {
           cin>>p[i];
           a[i]=i;
           }
           
           for(i=1;i<n;i++)
           {
            j=0;
            val=a[i];
            k=i;
            while(j<p[i])
            { 
             a[k]=a[k-1];
             k--;
             j++;
            }
            a[k]=val;
           }
    
           for(i=0;i<n;i++)
           p[a[i]]=i+1;
                      
           for(i=0;i<n;i++)
           cout<<p[i]<<" ";
           cout<<endl;
           
    }           
           system("pause");
           return 0;
}

[writetonsharma]

You have to tell what you are trying to do.

[ne555]

> what I should do to improve the running time.
Change your approach.


By the way, you are leaking memory.
And if you submit that to the judge, there must not be a system("pause")

[MiiNiPaa]

there must not be a system("pause")

That is probably the cause, actually: judge waiting for your program to stop, your program waiting for input. Time is up, your program is forcibly closed and you get "exceeded time limit" message

[ne555]

I doubt that the server has a `pause' command.

[writetonsharma]

generally looking at your code, I can add a couple of points.

- always do pre-increment to save couple of cycles unless it matters.
- don't unnecessary do I/O.
- You looks to be using C++, declare variables when they are actually required and not at the start of the function. This is 'C' style programming. This can sometimes save a lot of time.
- There are so many loop going from 0 - n; Surely there must be a way to reduce those.

This is just for the information -
All these are general rules and one cannot tell where the most of the time is consumed. professionally its done by performance analysis tools like gprof. These tools will tell you who's the culprit and then you can devote your time in specific part of the code rather than trying to find issues in the whole code. The tool is not tough to use. This generates a flat file and there are front ends to this tools also which can graphically depict all the paths of the code.

Now there are two things here - a part of code which takes 10 seconds and is called once. There is other part of code which takes .5 seconds but its called 50 times. So sometimes its tricky.

[ne555]

> always do pre-increment to save couple of cycles unless it matters.
small fish

> don't unnecessary do I/O.
define unnecessary. I/O communicates with the user, ¿how can that be superfluous?
(using the buffer will improve I/O)

> declare variables when they are actually required (...) This can sometimes save a lot of time.
¿how?

> There are so many loop going from 0 - n; Surely there must be a way to reduce those.
So you'll save a few increments, big deal.


The algorithm is O(n^2), that seems to be too much

[writetonsharma]

ne555 ... what I have written is true.. doesn't matter if the savings is small or big.. do you mean to say if we have good amount of savings then only we should indulge in good programming practices.

(using the buffer will improve I/O)

does this mean we write all the garbage to output ? buffer has to some point of time write to the output.

¿how?

Item 26, scott meyers.

So you'll save a few increments, big deal.

Again, looks like you want a savings of a million in one go. :-)

[cire]

Again, looks like you want a savings of a million in one go. :-)

Its always recommended when optimizing to change to a better algorithm when possible before spending time with micro-optimization of code (most of which will make very little, if any, difference.)

[paulrishav93]

I did not use system("pause") when submitting to the judge.

[paulrishav93]

I actually read somewhere that dynamic allocation of array takes a longer time. So, I defined a[100],p[100] in the beginning.
Now the judge tells me that I have a segmentation fault.
However, the program runs perfectly on Dev C++.
Where could the error be now?

[paulrishav93]

This is the question on SPOJ

http://www.spoj.com/problems/ORDERS/

[cire]

So, I defined a[100],p[100] in the beginning.

The first line contains a single integer n (1<=n<=200000).

I don't think space for 100 is enough space to hold up to 200000 objects.

[SamuelAdams]

Every cin statement is going to cause a delay while waiting on user input.
If you must use cin, at least put in a msg telling the user what is expected of them.

system("pause"); is a big no no, the program will sit there forever.

In my experience, if you have INT values, you always want to assign them to something, normally 0. I didn't look at the rest of your code since you have no comments.

[MiiNiPaa]

If you must use cin, at least put in a msg telling the user what is expected of them.

Please read OP post again: This program executes on server, with some input in predefined format and expecting some output in predefined format. So no unexpected output allowed.

TL;DR: The user is a machine, and it cannot read anything.