This Forum is in read only mode now.

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

×

SPOJ - HISTOGRA - Largest Rectangle in a Histogram help needed

Since I couldn't solve the problem myself, I read up the concept and codes and managed to get it submitted via a Divide and Conquer (divide from middle) approach and a stack based O(n) solution. I also came up with a segment tree solution but it seems to be giving me a wrong answer. I've referred to different segment tree solutions but can't seem to fix mine. Can anyone check out my approach and tell me what's wrong here? (It gives me correct answer on the test cases provided)

http://ideone.com/VDtOML

Thanks!

asked 15 Mar '17, 22:59

epsilonalpha's gravatar image

3★epsilonalpha
10516
accept rate: 25%


@epsilonalpha: You are getting WA because your approach is not right. Though you are finding out minimum number in the range using your query function, but you are not considering that number. I mean that you are using divide and conquer directly by dividing the array from the middle. Instead of this, you need to select the index of the minimum number that you are finding as middle index and then divide the array from that index.

I am giving you a example that why your approach is not right.

Consider the following array of heights and visit below link to see a photo describing how your query function is working.

Array: [2 3 3 1]
Link: Histogram

According to your solution, the array range [0,2] will never be considered which is indeed the correct answer. In a photo, The blocks in the merging are showing the answer in that range.

Visit this link given by @akshaym_96 for the correct solution using divide and conquer.

link

answered 17 Mar '17, 15:50

black_well's gravatar image

5★black_well
642
accept rate: 40%

Thanks, the example helped and now I got it submitted!

(17 Mar '17, 20:05) epsilonalpha3★
link

answered 15 Mar '17, 23:27

akshaym_96's gravatar image

3★akshaym_96
1506
accept rate: 13%

I've already tried reading those and I still couldn't get my segment tree solution accepted.

(17 Mar '17, 03:35) epsilonalpha3★

See this code. It's and simple and no need of segment tree

link

answered 15 Mar '17, 23:11

bansal1232's gravatar image

3★bansal1232
2.8k1419
accept rate: 16%

I have got the code submitted via two different methods including the stack based approach you just gave link to, I just need to submit it via a segment tree once. I can't figure out my mistake.

(17 Mar '17, 03:36) epsilonalpha3★

The problem has been solved. Here's the AC solution using Segment Trees for anyone needing this in future. http://ideone.com/H6LYjx

link

answered 17 Mar '17, 20:06

epsilonalpha's gravatar image

3★epsilonalpha
10516
accept rate: 25%

https://ideone.com/gRTOfr why does my code gives Time limit exceed error all the time ... i have used the stack approach to solve the problem.

link

answered 25 Mar, 02:03

niku_0609's gravatar image

2★niku_0609
1
accept rate: 0%

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,140
×711
×239
×116
×10
×6
×1

question asked: 15 Mar '17, 22:59

question was seen: 1,464 times

last updated: 25 Mar, 02:03