theviralv's blog

Common stack problems
By theviralv, history, 5 years ago, In English

I tried to solve problems like : 1. SPOJ POSTERIN 2. SPOJ HISTOGRA 3. Codeforces C2.Skyscrapers But i could not even understand the logic behind the stack based O(n) solution of above problems. Can anybody help.

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

For the Skyscrapers problem, you want to know for each index $$$i$$$ from $$$1$$$ to $$$n$$$, what is the optimal sum for buildings if you chose $$$i$$$ as your peak. Let's first focus on only the buildings on one side, e.g the left.

As you iterate from $$$1$$$ to $$$n$$$, you'll note that you need to replace all buildings to the left of your index that are higher than your current index, and that the resultant partial array is always monotonic (non-decreasing), however doing this naively could take $$$O(n^2)$$$ in the worst case scenario of a descending array.

However, if you maintain a stack of pairs $$$(value, num)$$$ that represent "blocks" instead, you can simply pop all blocks that have a $$$value$$$ greater than your current value, add all the removed $$$num$$$ values $$$+1$$$, then add them all back as one big block. As you're only adding one block per index, and you can only remove blocks previously added, this procedure runs in $$$O(n)$$$

To find the similar sum for buildings to the right of the index, simply reverse $$$m$$$ and run the procedure again, then reverse the result array. Then find the $$$n$$$ possible scores by combining the results, and find the best peak. Once the peak is found, the answer is easily reconstructed in $$$O(n)$$$.

Sample: 71830463

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes i know the process but i cannot figure out the logic behind the process like how it is correct. Also please can you explain spoj posterin problem

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 6   Vote: I like it +10 Vote: I do not like it

      You can imagine each block in the stack as representing $$$num$$$ copies of $$$value$$$; combining them this way just makes it fit in $$$O(n)$$$

      E.g. Say your stack already contains $$$m_{1..4} = 2, 3, 5, 6$$$ and $$$m_5$$$ is $$$4$$$. To find the "left score" for this index, all buildings that are higher than it in the stack must be decreased. So you want the end state to be $$$2, 3, 4, 4, 4$$$, but note that after removing the $$$5, 6$$$ you need to add $$$3$$$ copies of $$$4$$$, so it's better to just use the "block"s instead. Then $$$leftscore_i = \text {sum of stack}$$$, which can be maintained whenever you remove or add blocks.

      If later another even lower value is found, e.g. $$$1$$$, the block of three $$$4$$$'s can also be removed as a single unit.

      → Reply