E)Block Sequence
Hint 1
What shall we do in order to keep the top view same as the original?
Hint 2
What shall we do in order to keep the right side view the same as the original?
Approach
- If we assume the stack of blocks as a matrix:
-
- rows are represented the height of blocks at each index that is a[i].
-
- Columns are represented by the indices
In order for the top and right side view to be the same two things should be fulfilled
-
-
- In order to maintain the same top view from the original view, all columns containing blocks should leave at least one block remaining when the rest are removed. This way, the top view will remain unchanged.
-
-
-
- To maintain the right side view of the stack of blocks, it is necessary to keep at least one block in each row, starting from Row = 0 up to the maximum height of the stack.
-
- To make the right side views of blocks the same would be to use blocks which have minimum heights in order to cover up rows with minimum values. While doing this we have to make sure there is at least on block that is left in each column.
- Example: a = [2, 3, 1, 4, 4] In order to make the right side view of the blocks identical to the original, all stacks of blocks with a height ranging from 1 to 4 must be present in each row between rows 1 and 4.
The first block should be placed at index 2, to cover the row of 1. The second block should be placed at index 0 and will cover a row of 2. The third block should be placed at index 1 and will cover a value of 3. Finally, the fourth block can either be placed at index 3. Since we have to make sure that one block should be left at each index we can leave one block at index 4 and remove the rest.
Time Complexity: O(n.log n)
Code
def main():
num_stacks, height_of_exhibit = map(int, input().split())
heights = list(map(int, input().split()))
height_to_build = 1
max_height = max(heights)
heights.sort()
ans = 0
for i in range(num_stacks):
#we leave one block in each column and remove the rest
ans += (heights[i] - 1)
#if the current height is built move to the next
if heights[i] >= height_to_build:
height_to_build += 1
#subtract number of unbuilt heights from answer
ans -= (max_height - height_to_build + 1)
print(ans)
main()