Finding Time for Buildings to Submerge in Lava
Problem Statement
For each building in a given list, we need to determine the time for which it submerges into lava. A building submerges into lava if the lava level reaches at least the height of the building. The level of lava increases by p
units per unit time, where p
is provided as an input.
Approach
The key idea is to identify the nearest taller building that acts as a bottleneck for the i-th
building, preventing lava from flowing further. Since there is at least one volcano in the array (indicated by a height of 0
), we can use this information to optimize our approach.
Steps:
-
Find nearest taller buildings:
- Compute the prefix maximum and suffix maximum for every element in the array. These values help determine the nearest taller building on either side of a given building.
- The effective height controlling lava flow for the
i-th
building is the minimum of these two values:min(prefix[i], suffix[i])
.
-
Handle cases where the array does not start and end with a volcano:
- Locate the leftmost (
l
) and rightmost (r
) indices where the building height is0
. - Compute suffix maximum for indices less than
l
. - Compute prefix maximum for indices greater than
r
.
- Locate the leftmost (
-
Compute the submersion time:
- Divide the effective height of each building by
p
and use ceiling to get the minimum time required for submersion.
- Divide the effective height of each building by
Python Implementation
import math
def find_submersion_time():
t = int(input())
for _ in range(t):
n, p = map(int, input().split())
arr = list(map(int, input().split()))
# Find leftmost and rightmost volcano
l = arr.index(0)
r = n - arr[::-1].index(0) - 1
# Initialize prefix and suffix maximum arrays
pre = [0] * n
suf = [0] * n
# Compute prefix max for elements between leftmost and rightmost volcano
for i in range(l + 1, r):
if arr[i] == 0:
pre[i] = 0
else:
pre[i] = max(pre[i - 1], arr[i])
# Compute suffix max for elements between rightmost and leftmost volcano
for i in range(r - 1, l, -1):
if arr[i] == 0:
suf[i] = 0
else:
suf[i] = max(suf[i + 1], arr[i])
# Find the nearest taller building for each index
for i in range(n):
pre[i] = min(pre[i], suf[i])
# Compute max prefix for elements before leftmost volcano
for i in range(l - 1, -1, -1):
pre[i] = max(pre[i + 1], arr[i])
# Compute max suffix for elements after rightmost volcano
for j in range(r + 1, n):
pre[j] = max(pre[j - 1], arr[j])
# Compute submersion times
res = [math.ceil(pre[i] / p) for i in range(n)]
# Print results
print(" ".join(map(str, res)))
Complexity Analysis
- Finding
l
andr
:O(n)
- Computing prefix and suffix maximums:
O(n)
- Computing submersion times:
O(n)
- Overall Complexity:
O(n)
, making the approach efficient for large inputs.
Example Input & Output
Input:
1
7 2
3 1 0 5 2 4 0
Output:
2 1 0 3 1 2 0
This means that each building will submerge into lava within the given times, based on the increasing lava level.
Conclusion
This approach efficiently calculates the minimum time required for each building to submerge into lava, handling edge cases where buildings are surrounded by multiple volcanoes.