codinghermit05's blog

Users Solutions greyed out. Unable to view Editorial or Solution. Please help :(
By codinghermit05, 3 years ago, In English

Submissions to some old problems (without clear editorials or solutions) are greyed out. How can I know the solution to such problems in Codeforces?

The problem I am trying to learn: https://mirror.codeforces.com/gym/102760/problem/F

Words on Editorial: "There is another, more difficult solution. If you know how to find the largest rectangle in the histogram inO(N) using a stack, then you may realize that you can actually apply the exact same strategy to find the largest square. The proof is left to the reader for exercise."

And my solution 

n = int(input())
arr = list(map(int, input().split()))

def solve(heights):
    maxside = 0
    pstack, hstack = [], []
    currarea, maxside = 0, 0
    heights.append(0)
    for i in range(len(heights)):
        prevwidth = int(1e9)
        while hstack != [] and hstack[-1] > heights[i]: # -_
            prevwidth = pstack[-1]
            width = i - pstack.pop()
            height = hstack.pop()
            if width == height:
                maxside = max(maxside, width)
        if maxside < heights[i] or not hstack or hstack[-1] < heights[i]: # _-
            hstack.append(heights[i])
            pstack.append(min(prevwidth, i))
    return maxside

ans = solve(arr)
print(ans)
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Largest Square under a histogram can be calculated using 2 Stacks, one for heights and one for indices.

n = int(input())
arr = list(map(int, input().split()))
def solve(heights): # O(n) solution using Stacks
    pstack, hstack = [], []
    maxside, currarea, maxside = 0, 0, 0
    heights.append(0)   # to finish off the remaining items in the stack
    for i in range(len(heights)):
        prevwidth = int(1e9)
        while hstack != [] and hstack[-1] > heights[i]: # negative slope
            prevwidth = pstack[-1]
            maxside = max(maxside, min(hstack.pop(), i - pstack.pop()))
        if not hstack or hstack[-1] < heights[i]: # positive slope
            hstack.append(heights[i])
            pstack.append(min(prevwidth, i))
    return maxside
res = solve(arr)
print(res)
→ Reply