You are not logged in. Please login at www.codechef.com to post your questions!

×

SPOJ Histogram Help

I was trying to decode the logic in SPOJ HISTOGRA problem but couldn't think of any good solution. So, I referred this link. Now, I do get the logic behind this problem but now I am stuck at one part. Here's my understanding: 1. We traverse the array from left to right 2. If the stack is empty or if a[i+1]th element is greater than a[i] then we push 3. If the next element is smaller than we pop and then we calculate the popped element's area. Now, I am stuck at the step after this. I don't seem to understand how to calculate the area of the popped element. I mean, with respect to which elements should I be calculating the area? The link I'm referring to says it should bearea_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);. I am not able to map this statement. Yes, I do know this ternary condition's output but I am not able to understand how the area is calculated with hist[tp]

asked 24 Oct '17, 22:09

montycs's gravatar image

0★montycs
1057
accept rate: 0%


Actually, its quite easy. The critical point is that, i is NOT incremented after calculating area. Its only incremented when adding a new element in stack.

How this statement executes is like this-

  1. We encountered an element whose height is less than height at top of stack.
  2. Now we will calculate area using heights which are > this height.
  3. Assuming stack is NOT empty for condition ((s.empty() ? i : i - s.top() - 1);
  4. The height at immediate top is maximum. For this, i - s.top() - 1 evaluates to 1 - which is the width
  5. That element is popped. Now the next element at top of stack is checked.
  6. If its height is also > height at hist[i], we consider this as minimum height. Now i - s.top() - 1 evaluates to 2. In other words, New width=old width+1. (Geometric interpretation- The rectangle is being made out of histograms occurring after this histogram- as their height is guaranteed to be >= hist[st.top()])
  7. Lets say our histogram is [5,5,5,1]. It pushes {5,5,5} into stack. Now it comes to 1. 5>1 , and width for it is returned as 1 (verify yourself). Area1= 5*1=5. Then next 5 is taken. Its width is 1 more than previous, which is 2. New area =5*2=10. Then next 5 is popped and this time width is 3. Now area =15. Since stack is empty now, we push i to stack and proceed accordingly.
  8. What does it mean if stack is empty in ((s.empty() ? i : i - s.top() - 1);?
  9. It means that we encountered a global minimum. The width for this minimum, at this step, should be 1+1+1...i times (since we can make a rectangle of this height in all i histograms).
link

answered 24 Oct '17, 23:23

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 24 Oct '17, 23:26

Please be honest with me.. Did you crack the logic in the first go when you first came across this problem?

(28 Oct '17, 20:37) montycs0★

The basic idea for this question is to find the next and previous smallest element for each of the elements of the array. This can be done in O(n) using stack.

Now for each element a[i] you can find the ends of the histogram of height a[i] and which passes through i.

If you want link to my solution.

link

answered 25 Oct '17, 00:09

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,136
×862
×173

question asked: 24 Oct '17, 22:09

question was seen: 383 times

last updated: 28 Oct '17, 20:37