FRIHOST FORUMS SEARCH FAQ TOS BLOGS COMPETITIONS
You are invited to Log in or Register a free Frihost Account!


Make c++ script more efficient?





speeDemon
Hi, I recently participated in a national level computer programming exam, but unfortunately my code exceeded the time limit provided (2 seconds) for solving test cases. So, well, I wasn't selected for the final camp to be held in june, but anyhow, I wanted to know how to make this code better, faster, more efficient.

Now, I use Turbo C++, as that is what they teach in school, but the competition required me to use Dev C++ compiler, so whatever you suggest, I think it would be better if its something that would also work on Turbo C++, I mean to say, its better if you don't use commands like std::something(something I dont know about).

I'll post the questions they gave me (2), and the code I provided
speeDemon
OK, so the first question was,
There is a certain town, and in this town there is an annual fest, like a founders day or something.
The Leader of the people has arranged a competition on this occasion.
You have to go through 3 different tasks in the same order: A computer programming contest, Pole Vault and Doughnut eating.

The issue is that there is only 1 computer in the city, and everyone must first go to the computer, then the pole vault and finally the doughnut. The other two contests can run simultaneously for any number of contestants. In a way, the "track" for the other two can be utilised by any number of people at any given time, but the computer is only 1.

Now the leader knows everyone personally in town, so he knows the time each person will take in completing each task.

You are given N number of people, and in the following lines, the time they take the computer contest, pole vault and doughnut eating (all in one line) in that same order.

You have to display the minimum amount of time in which the event can possible finish.

My code:
Code:


#include<iostream>
//#include<conio.h>
#include<limits.h>


using namespace std;

int Doit(int[][2],int[]);
int sumI(int[][2],int,int[]);

int minTime=INT_MIN,nest=0,numCitGlobal,sumTotal=0;

int main()
{
   int tmp;
   cin>>tmp;
   const int numCit=tmp;
   
   int Ar[numCit][2],access[numCit];
   numCitGlobal=tmp;
   
   for(int i=0;i<numCit;i++)
   {
       cin>>Ar[i][0];
       cin>>Ar[i][1];
       cin>>tmp;
       Ar[i][1]+=tmp;
       Ar[i][1]+=Ar[i][0];
       access[i]=1;
   }
   
   
   
   //for(int i=0;i<numCit;i++)
   {
        Doit(Ar,access);         
   } 
   
   cout<<minTime;
 //getch();
   
}

int Doit(int ar[][2],int access1[])
{
    int min=INT_MAX;
    int sum,pos;
    nest++;
    if(nest>numCitGlobal)
    {
      nest--;
      return 0;
    }
   
   
    for(int i=0;i<numCitGlobal;i++)
    {
         if(access1[i]!=0)
         {
         access1[i]=0;
         sum=ar[i][1];
         for(int j=0;j<numCitGlobal;j++)
         {
               if(access1[j]!=0)
               sum+=ar[j][0];
         }
         if(sum<min)
         {
              min=sum;
              pos=i;
         }
                   
         access1[i]=1;       
         }       
    }
   
    if(sumI(ar,pos,access1)>minTime)
    minTime=sumI(ar,pos,access1);
   
   
    access1[pos]=0;//cout<<"Take row "<<pos<<" as "<<numCitGlobal-(nest-1)<<endl;
    Doit(ar,access1);
    nest--;
    return 0;   
           
}

int sumI(int ar[][2],int pos,int access1[])
{
    int sum=ar[pos][1];
    access1[pos]=0;
    for(int j=0;j<numCitGlobal;j++)
         {
               if(access1[j]!=0)
               sum+=ar[j][0];
         }
         
    return sum;
}

speeDemon
The second question was,
There is a table, with two rows, and N number of columns, now, the first row's elements will be given as input, the second row's elements are
1,2,3,4... N

The arrangement of the elements of the second row can be in N ways, by shifting all the elements to the left, and making the first element last.

so, for example, if I have the first row as
12 34 56 67
1 2 3 4
or
2 3 4 1
or
3 4 1 2
or
4 1 2 3

Now, the score of a table is defined as the Sum of the elements of the column, which is the largest in all columns, as in,
for the first table,
12 34 56 67
1 2 3 4

The sum of elements of the columns are, 13, 16,59,71
so the score is 71. Similarly, you can find the score for the other 3 tables,

You have to give as output, the score of all the tables, in that same order, that is, the second table will be

12 34 56 67
2 3 4 1

and so on...

My code:
Code:

#include<iostream>
//#include<conio.h>
#include<limits.h>

using namespace std;
int numColGlobal;
int Score(int[],int[],int);

int main()
{
 int tmp;
 cin>>tmp;
 const int numCol=tmp;
 numColGlobal=tmp;
 int Ar1[numCol];
 int Ar2[numCol];
 
 for(int i=0;i<numCol;i++)
 {
      cin>>Ar1[i];
      Ar2[i]=i+1;
 }
 
 
 for(int i=0;i<numCol;i++)
 {
     cout<<Score(Ar1,Ar2,i);       
 }
 
//getch();
 return 0;
}
   
int Score(int ar1[],int ar2[],int pos)
{
 int max=INT_MIN,tmp=0,index;
 //cout<<"Entered Score with pos="<<pos<<endl;
 for(int i=0;i<numColGlobal;i++)
 {
//      cout<<"Entered for i="<<i<<endl;
      tmp=0;
      index=i+pos;//cout<<"Index set as "<<index<<endl;
      if(index>numColGlobal-1)
      {
         index-=numColGlobal;//cout<<"index was bigger than "<<numColGlobal<<" now set as "<<index<<endl;                   
      }
      tmp=ar1[i]+ar2[index];//cout<<"tmp set as "<<ar1[i]<<"+"<<ar2[index]<<endl;
      if(tmp>max)           
      {
         max=tmp;//cout<<"Max is now = "<<tmp<<endl;           
      }
 }
//cout<<"Returning max="<<max<<endl;
return max;
}   
speeDemon
I would appreciate any kind of helpful tips, like maybe, dont use global variables or well, just about anything, or you can just provide an alternate logic, for more efficient execution!
Peterssidan
Do you know what optimizations settings they used? Both Dev-C++ and Turbo C++ use quite old compilers and is not up to date with later C++ standards. Newer compilers have many improvements and is much better in optimizing code. I haven't looked at the code much yet but I will do that later.
Peterssidan
Ok I have now taken a look at the first question.

I found it a bit hard to read your code. Many of the variable and function names could have been more descriptive. I guess Ar stands for array but that doesn't say much about what it represents. access? I guess it has something to do with access to the computer but it's not really clear. It looks like access is used as boolean values so I think it would be better to make it a bool array instead.

The function DoIt. It does something alright but what is it doing? You seem to get the correct answers so I guess it works.

I wrote an implementation just to test, and the way I did it was to first sort all the contestants so that all contestants that spend most time on pole vaulting and doughnut eating comes first. This makes the optimal order. Then I just have to sum the computer times and keep track of any rest time from pole vaulting and doughnut eating and add that at the end to get the minimum time.

Code:
#include <iostream>
#include <algorithm>
#include <vector>

// struct to keep time information about contestants
struct Contestant
{
   int computerTime;
   int poleVaultAndDoughnutTime;
};

// comparasion function to be used for sorting
bool ContestantCmp(const Contestant& c1, const Contestant& c2)
{
   return c1.poleVaultAndDoughnutTime > c2.poleVaultAndDoughnutTime;
}

int main()
{
   // number of contestants
   int nContestants;
   std::cin >> nContestants;
   std::vector<Contestant> contestants(nContestants);
   
   // read in the times
   for(int i = 0; i < nContestants; i++)
   {
      int computerTime;
      int poleVaultTime;
      int doughnutTime;
      
      std::cin >> computerTime;
      std::cin >> poleVaultTime;
      std::cin >> doughnutTime;
      
      contestants[i].computerTime = computerTime;
      contestants[i].poleVaultAndDoughnutTime = poleVaultTime + doughnutTime;
   }
   
   // sort the contestants by pole vaulting and doughnut eating time
   std::sort(contestants.begin(), contestants.end(), ContestantCmp);
   
   // calculate the minimum time
   int time = 0;
   int restTime = 0;
   for(int i = 0; i < nContestants; i++)
   {
      time += contestants[i].computerTime;
      restTime = std::max(contestants[i].poleVaultAndDoughnutTime, restTime - contestants[i].computerTime);
   }
   time += restTime;
   
   std::cout << time << std::endl;
}


I have used GCC 4.7 so you might have to make changes to make it work in Turbo C++ or Dev-C++.

This code will run in O(n*log(n)) while your code will run in O(n^3) I believe so this should be faster.
Peterssidan
The second question.

Your code has O(n^2) time complexity but I can't see how to improve that.

You don't really need Ar2 because you can easily calculate the value from i and pos by doing (i+pos)%numColGlobal+1.
speeDemon
Did you consider the fact that whoever comes 2nd, third, 4th and so on, will have the time of the previous contestants time on the computer..?
Eg;

Sno Computer Pole Vault Doughnut Eating
1)..........45.............67................76
2)..........30.............34................48
3)..........50.............20................32

now, if the order we take is 2,then 3,then 1.
the times will be: for 2 = 30+34+48........=112
.........................for 3 = 30+50+20+32.......=132
.........................for 1 = 30+50+45+67+76 =268

So, if we go by this method/order, the minimum time in which the event can end is 268...
I'm not quite sure about your logic, as in, I didn't think that much right now, just wanted to make sure you took all this into consideration Razz
Peterssidan
2, 3, 1 is not the optimal order. The optimal order is 1, 2, 3 which gives the minimal time 188. And yes it takes into consideration the previous contestants time on the computer (this line: time += contestants[i].computerTime;).

The way I thought was this. The sum of all computer times will always be constant and the end time will only depend on how much time we have to spend waiting for pole vaulting and doughnut eating that hasn't finished. By doing pole vaulting and doughnut eating that takes more time first we have more time to spend on these so they are will affect the end time as little as possible or not at all.
speeDemon
my basic mechanism was that,
I would rule out the person going last, and then out of the rest of the people who will go last, so on,
and at each stage, calculate the time taken by this certain person, if it's more than whatever minimum I've set, then well, set it accordingly...
speeDemon
Peterssidan wrote:
2, 3, 1 is not the optimal order. The optimal order is 1, 2, 3 which gives the minimal time 188. And yes it takes into consideration the previous contestants time on the computer (this line: time += contestants[i].computerTime;).

The way I thought was this. The sum of all computer times will always be constant and the end time will only depend on how much time we have to spend waiting for pole vaulting and doughnut eating that hasn't finished. By doing pole vaulting and doughnut eating that takes more time first we have more time to spend on these so they are will affect the end time as little as possible or not at all.


Damn, that makes perfect sense Razz !!! I'm an idiot!!
Agghhh I always complicate things, for no apparent reason...!!
Fire Boar
So this is pretty much a time complexity problem. If there is a time limit on test cases then that immediately should be sending up red flags. O(N) (three nested recursions: recursion of doIt and two for loops) is pretty grisly for polynomial time, while O(N log N) is a classic favourite of problem setters.

The second problem is also a complexity problem. The nave algorithm is O(N). To improve this, a little creative thinking is required. The worst case complexity of the best algorithm is O(NM), where M is the number of input elements that differ from the largest element by no more than N - 1. 1 <= M <= N, but usually M is much smaller than N. Here's how the algorithm works.

The score of a table is the highest scoring column, but the score of column k is input k plus some value from 1 to N. First make two passes over the input array. The purpose of the first pass is to determine the largest input value maxInput, and the purpose of the second is to figure out what M is. Create an array A of size M, and pass over the input array, adding pairs (x,y) to it. Here x is the input in that column, and y is the 1-based column index. Add a pair only if x + N > maxInput. All this takes time O(N).

Iterate over A, working out max{x+y : (x,y) in A} and printing it. After examining each pair, set y = (y % N) + 1 ready for the next run. Repeat N times to get all your different totals in order as required. This takes time O(MN).
speeDemon
could you please explain the way you're writing the execution time, I've never heard about O(N log N) O(MN), or any such phrase, how do I comprehend these..?
abhinavm24
Speed demon its just the time complexity representation, it smeant to represent the worst case scenario time required by the code to execute.
for example:O(n) == for 'n' number of input to the program, it would take linear time dependency like 2*n,0.132*n etc where constant is inherent from the device the code is executed upon.

so nlog(n) is lesser processing time as compared to n^2 or n^3 counterpart and hence infer the faster code execution or lesser execution time,i.e. what you always aim for while coding solutions to such problems.

usually time complexity of n^3 or higher is considered to a useless code to solve a problem*
and should be used only if you are sure of the code solving the problem even in the worst case and turn up with a soltion, if you aren't try optimizing the code for better execution times.
hopefully i helped. Very Happy
Related topics
Join Online Classes - 5 Frih$ to Join!
need help debugging C++ script.
Frihost's IRC Channel is Back in Order
Sending arbitrary data to/from PHP
C++ Software
I like School Computers
[Automation] Script language with C-like syntax
script backup database
Un script installer? laissez faire frihost!
Creating an RPG bot in IRC (yes I wrote this)
[Question] Visual Basic C++, PHP, mySQL language guides...
Programming links, info, and tutorials
MySQL DB Backup script - minor problem
Suggest a Free or Trial classifieds script
Reply to topic    Frihost Forum Index -> Scripting -> Others

FRIHOST HOME | FAQ | TOS | ABOUT US | CONTACT US | SITE MAP
© 2005-2011 Frihost, forums powered by phpBB.