Volcanic Eruption (Linear time and space complexity)

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:

  1. 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]).
  2. 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 is 0.
    • Compute suffix maximum for indices less than l.
    • Compute prefix maximum for indices greater than r.
  3. Compute the submersion time:

    • Divide the effective height of each building by p and use ceiling to get the minimum time required for submersion.

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 and r: 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.

big fan bro

1 Like

Same way, my code:

import math


for _ in range(int(input())):
    n, p = list(map(int, input().split(" ")))
    ns = list(map(int, input().split(" ")))

    pre = [0] * n
    pre[0] = ns[0]
    for i in range(1, n):
        if ns[i] == 0:
            pre[i] = 0
        else:
            pre[i] = max(pre[i - 1], ns[i])
    suf = [0] * n
    suf[-1] = ns[-1]
    for i in range(n - 2, -1, -1):
        if ns[i] == 0:
            suf[i] = 0
        else:
            suf[i] = max(suf[i + 1], ns[i])

    left, right = None, None
    for i, h in enumerate(ns):
        if h == 0:
            if left is None:
                left = i
            right = i

    ans = list()
    for i, h in enumerate(ns):
        if h == 0:
            ans.append(0)
            continue
        if i < left:
            right_max = max(suf[i + 1], h)
            ans.append(math.ceil(right_max / p))
        elif i > right:
            left_max = max(pre[i - 1], h)
            ans.append(math.ceil(left_max / p))
        else:
            left_max = max(pre[i - 1], h)
            right_max = max(suf[i + 1], h)
            ans.append(min(math.ceil(right_max / p), math.ceil(left_max / p)))

    print(" ".join(map(str, ans)))

By the way, my solution for WhiteWall has a bug(cause runtime error), but I can’t find it, could you help me to analyze where the problem is? thx~
Link: https://discuss.codechef.com/t/help-me-in-solving-whitewall-problem/122480