trjhtr

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable bucketCount describe how many buckets are placed on tower (1 <= bucketCount <= 10^6). We set buckets in sequence. Thickness of bucket is 0 (for simplicity)

Image of example tower:

I decided to use a stack. My algorithm for each bucket:

1. If stack is empty, then push bucket to stack.


2. If the bucket I hold is narrower then bucket on top then put it on the stack.


3. Else while bucket I hold is wider: pop and find maximum height (for new bucket ground), after that push bucket which I hold.

For each bucket I added additional an variable ground, which specifies the height at which the bucket is placed. Meantime I keep maximum height of tower in variable.

This task is automatically checked and gives output: time limit exceeded. I tried to optimize code but nothing gives positive result.

Example input: 2 20 20 30 30

Output: 50

#include <iostream>
#include <stack>

using namespace std;

struct Bucket
public:
 int height;
 int radius;
 int ground;
;

int main()

 int ile;
 cin >> ile;
 for(int c = 0; c < ile; c++)
 stack<Bucket> tower;
 int hightestPoint = 0;
 int bucketCount;
 cin >> bucketCount;
 Bucket temp; 
 Bucket temporary; //Used to speed up a bit 
 int maksimum;
 int sum;
 int counter = 0; //Its size of the Stack. Used it because thought its faster then empty() function
 for(int i = 0; i < bucketCount; i++)
 cin >> temp.radius >> temp.height;
 maksimum = -1;
 sum = 0;
 if(counter == 0)
 temp.ground = 0;
 tower.push(temp);
 counter++;
 else 
 if(temp.radius < tower.top().radius) //If bucket is narrower then push it
 temp.ground = tower.top().ground;
 tower.push(temp);
 counter++;
 else //If bucket is wider
 while((counter > 0) && temp.radius >= (temporary = tower.top()).radius) //Pop and search for new ground (maximum)
 sum = temporary.height + temporary.ground;
 if(maksimum < sum)
 maksimum = sum;
 
 tower.pop();
 counter--;
 
 temp.ground = maksimum; //Set ground for new bucket
 tower.push(temp);
 counter++;
 
 
 sum = temp.height + temp.ground; //Meantime find highest point in stack
 if(hightestPoint < sum)
 hightestPoint = sum;
 
 
 cout << hightestPoint << endl;
 


 return 0;

You don't need to remember every single bucket you've seen.

Once a bucket is added to the top of the pile, any wider bucket that has its rim lower than the rim of the new bucket becomes irrelevant, as do all the narrower buckets it sits on.

So a better data structure would just store the altitudes of all rims currently in play; this can be initialised to (0,0). When you add a bucket, find the widest rim not greater than the new bucket's width; we now set height[0] to that height and height[bucket_width] to height[0]+bucket_height. Remove all narrower buckets, and all other buckets up to a the new height - they can no longer affect the result.

Other items for review:

• 
  

  using namespace std;
  

  
  
  

  Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

  
  



• Spellings: highestPoint, maximum.



• Naming: temp and temporary - these are declared far from their use, so it's hard to appreciate the difference.


• You can omit return 0; in main().