We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Painting the Walls

Number: 2808

Difficulty: Hard

Paid? No

Companies: Snowflake, DE Shaw, Meesho, Microsoft, Google, Amazon, Adobe, Media.net, Apple, Bloomberg

Problem Description

You are given two 0-indexed arrays, cost and time, representing the cost and time taken by a paid painter to paint n walls. Additionally, there is a free painter who can paint any wall in 1 unit of time at zero cost—but can only work when the paid painter is busy painting. In other words, if the paid painter paints a set S of walls, taking time[i] for each wall i in S (painted sequentially), then in parallel the free painter can paint at most (sum of time[i] for i in S) walls (since he takes 1 unit per wall). The goal is to choose a subset of walls for the paid painter (incurring the given cost) such that the free painter can cover the remaining walls within that busy time. Formally, if |S| is the number of walls painted by the paid painter and T is the total time he spends (sum time[i] for i in S), we must have: (n – |S|) ≤ T. Equivalently, T + |S| ≥ n. The task is to minimize the total cost spent by the paid painter.

Key Insights

  • The free painter can only paint a wall concurrently when the paid painter is busy.
  • If the paid painter paints a wall, he consumes time[i] units and contributes “1” to the count of walls he paints.
  • The free painter can paint at most T walls when the paid painter takes T total time.
  • Reformulate the problem: choose a subset S of walls so that (sum(time[i] for i in S) + |S|) ≥ n and minimize sum(cost[i] for i in S).
  • This is similar to a knapSack problem where each wall i has a "value" of (time[i] + 1) at a "cost" of cost[i] and we want to achieve at least a total value of n.

Space and Time Complexity

Time Complexity: O(n * (n + sum(time))) where n ≤ 500 and each time[i] ≤ 500, resulting in a worst-case pseudo-polynomial factor. Space Complexity: O(n + sum(time)) for the DP array.

Solution

We solve the problem using dynamic programming modeled as a knapSack problem. Define dp[v] as the minimum cost to achieve a total “value” v, where for every wall chosen by the paid painter, we add (time[i] + 1) to the value and cost[i] to the cost. Initially, dp[0] = 0, and dp[v] = infinity for all v > 0. For each wall, iterate backwards over possible current values to avoid counting the same element more than once, and update dp[v + (time[i] + 1)] accordingly. Finally, the answer is the minimum cost among all dp[v] for v ≥ n as this condition guarantees that the paid painter’s total time plus the count of walls painted meets the required threshold.

Code Solutions

# Python solution with line-by-line comments
def paintingWalls(cost, time):
    n = len(cost)
    # Maximum achievable value is sum(time) + n (each wall contributes time + 1)
    max_value = sum(time) + n
    # Initialize dp array with a large number representing infinity
    dp = [float('inf')] * (max_value + 1)
    dp[0] = 0  # cost 0 for achieving value 0
    
    # Process each wall
    for i in range(n):
        # value contributed by choosing the current wall is (time[i] + 1)
        wall_value = time[i] + 1
        # Traverse backwards to ensure each wall is used only once
        for v in range(max_value - wall_value, -1, -1):
            if dp[v] != float('inf'):
                dp[v + wall_value] = min(dp[v + wall_value], dp[v] + cost[i])
    
    # Find the minimum cost for any total value >= n
    answer = min(dp[v] for v in range(n, max_value + 1))
    return answer

# Example usage:
# cost = [1,2,3,2], time = [1,2,3,2] should output 3
print(paintingWalls([1,2,3,2], [1,2,3,2]))
← Back to All Questions