Tap here to switch tabs
Problem
Submissions

Problem: Paint House IV

Paint House IV gives painting costs for an even row of houses. Find the minimum cost to use three colors while keeping adjacent and mirrored houses different.

Statement

You are given an even integer n representing the number of houses arranged in a row, along with a 22D integer array cost of dimensions n $ imes$ 33, where cost[i][j] represents the cost to paint house i with color j.

You must paint every house using one of the 33 colors such that the following conditions are satisfied:

  • No two adjacent houses have the same color. That is, house i and house i + 1 must be painted with different colors for all 0≤i<n−10 \leq i < n - 1.

  • Houses that are equidistant from the opposite ends cannot have the same color. That is, house i and house $n - 1 - i$ must be painted with different colors for all 0≤i<n20 \leq i < \frac{n}{2}.

Return the minimum total cost needed to paint all the houses.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • n is even.

  • cost.length ==== n

  • cost[i].length ==3== 3

  • 0≤0 \leq cost[i][j] ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Paint House IV

Paint House IV gives painting costs for an even row of houses. Find the minimum cost to use three colors while keeping adjacent and mirrored houses different.

Statement

You are given an even integer n representing the number of houses arranged in a row, along with a 22D integer array cost of dimensions n $ imes$ 33, where cost[i][j] represents the cost to paint house i with color j.

You must paint every house using one of the 33 colors such that the following conditions are satisfied:

  • No two adjacent houses have the same color. That is, house i and house i + 1 must be painted with different colors for all 0≤i<n−10 \leq i < n - 1.

  • Houses that are equidistant from the opposite ends cannot have the same color. That is, house i and house $n - 1 - i$ must be painted with different colors for all 0≤i<n20 \leq i < \frac{n}{2}.

Return the minimum total cost needed to paint all the houses.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • n is even.

  • cost.length ==== n

  • cost[i].length ==3== 3

  • 0≤0 \leq cost[i][j] ≤105\leq 10^5