Help on a SPOJ Problem Dealing with Stacks

Problems and Contests
#1

Problem Link

I’ve been working on this problem for a bit, and I seem to be stuck on finding any sort of solution. I know that the solution for O(N) has to deal with stacks, but I can’t figure out how to properly utilize stacks for this problem.

Some things I’ve thought of:

  • I don’t think the widths matter at all, because the posters can be infinitely long, and just replacing all widths with 1 yields the same result (not 100% sure though)
  • The O(N^2) solution is to find the minimum height of the buildings, then subtract that height from all of the other heights. In essence, this would separate the buildings into their “layers.” Then, the answer would just be the number of times this process has to happen for all buildings to have a height of 0.

I am stuck on what the stack’s function actually will be. But more importantly, I am confused on when we should pop from the stack and what we should do with the top element of the stack.

Thank you in advance for any help!

EDIT: I just realized that the O(N^2) solution does not work after all. For example, if we had the input:

3
1 3
1 1
1 3

The program would output 2, when it should really be 3.

#2

The O(N^2) solution looks correct, why would it output 2?

Hint: First ignore the D_i, since they don’t affect the answer. The solution (which computes the answer for every prefix of buildings) ends up looking nearly the same as Nearest Smaller Element and the stack solution to No Time to Dry.

Code 
int main() {
	setIO();
	ints(N);
	stack<int> stk; stk.push(0);
	int ans = 0;
	rep(N) {
		ints(D,W);
		while (stk.top() > W) stk.pop();
		if (stk.top() < W) stk.push(W), ++ans;
	}
	ps(ans);
}
#3

Thank you! I figured out the solution once I wrote out a few more testcases and also looked closer at the solutions for the problems you linked. For the O(N^2) solution, I was thinking in the wrong way, I realized that we should separate the different “components,” once one of the building’s heights becomes 0. I was thinking to just subtract the minimum from all buildings instead of only those in its component.