# PROBLEM LINK:

*Author & Editorialist:* Karthikeya

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Dynamic Programming

# PROBLEM:

You are given an M size array **buildings**, where 0 \leq **buildings**[i] \leq N. You are also given an M \times N size **cost** matrix, where **cost**[i][j] represents replacing **buildings**[i] with a positive number j(1\leq j \leq N) if **buildings**[i] is 0 initially.

A community is a maximal subarray of buildings in which all the numbers are same. For example: **buildings** = [1,1,1,2,2,1,3,3,3] has 4 communities - \{(1,1,1),(2,2),(1),(3,3,3)\}.

Find the minimum total cost of replacing all the 0's with a positive number j(1\leq j \leq N) such that there are exactly K communities in **buildings**. If it is not possible to have K communities return -1.

# QUICK EXPLANATION:

We can solve this in O(N^2MK) by using Dynamic Programming,

**State:**

DP(i,j,k) represents minimum cost of replacing all 0's in the subarray **buildings**[1,2,...i] such that **buildings**[i] is j and this subarray has exactly k communities. (1\leq i \leq M, 1\leq j \leq N, 1\leq k \leq K).

**State Transition:**

# EXPLANATION:

This problem can be solved by Dynamic Programming. For any DP problem we need two things : **State** and **State transition**. So first let us define our state. To solve this problem we are using 3-dimensional DP.

**State:**

DP(i,j,k) represents minimum cost of replacing all 0's in the subarray **buildings**[1,2,...i] such that **buildings**[i] is j and this subarray has exactly k communities. (1\leq i \leq M, 1\leq j \leq N, 1\leq k \leq K).

Now let us figure out the state transition.

- Case 1: When \textbf{buildings}[i]=j, we can get k communities till i houses in two ways. One way is to have k communities such that the i^{th} building is the only one that belongs to k^{th} community, in this case we need to consider - min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\} as we require the minimum cost. The other way is by having more than 1 buildings in the k^{th} community, so for this \textbf{buildings}[i-1] has to have j floor, hence we need to consider - DP(i-1,j,k). So from DP(i,j,k) would be the minimum of these two costs. One more thing to consider is, the above transitions are valid only for k \geq i, if it is not the case then it is impossible to have k communities. So the transition for the first case is,

\text{if} \; (\textbf{buildings}[i] = j \: \text{and} \: k \leq i):

- Case 2: When \textbf{buildings}[i]=0, in this case as \textbf{buildings}[i] is 0, we have to construct a building at i^{th} position with j floors. So the cost of construction would be \textbf{cost}[i][j] and the same transition which we had in the previous case would add up as it is, because once we construct a j floors building at the i^{th} index, we reduced this case to the first case. So the transition for this case would be,

\text{if} \; (\textbf{buildings}[i] = 0 \: \text{and} \: k \leq i):

- In all other cases it is impossible to have k communities so we set the cost to \infin.

So the overall state transition would look like,

**State Transition:**

**Initialization**: One way to initialize is to add a dummy index at the beginning so the dimension of DP table would become (M+1 \times N+1 \times K+1) and make it all *zeros*. Now set the DP[0][j][k] and DP[i][j][0] to \infin \forall i,j,k satisfying the constraints.

# TIME COMPLEXITY:

Time: O(N^2MK)

Space: O(NMK)

Note : Time can be reduced to O(NMK) and space can be reduced to O(NK) as this was the 3^{rd} question in the contest we set weaker constraints.

# SOLUTION:

## Setter's Solution

**Setters Solution:**

```
def minCost(buildings, cost, m, n, k):
t = k
dp = [[[0 for i in range(t+1)] for j in range(n+1)] for i in range(m+1)]
for k in range(1,t+1):
for j in range(1,n+1):
dp[0][j][k] = float('inf')
for i in range(1,m+1):
for j in range(1,n+1):
dp[i][j][0] = float('inf')
for i in range(1,m+1):
for j in range(1,n+1):
for k in range(1,t+1):
if buildings[i-1] == j and k<=i:
dp[i][j][k] = min(dp[i-1][j][k],min([dp[i-1][p][k-1] if p!=j else float('inf') for p in range(1,n+1)]))
elif buildings[i-1]==0 and k<=i:
dp[i][j][k] = cost[i-1][j-1]+min(dp[i-1][j][k],min([dp[i-1][p][k-1] if p!=j else float('inf') for p in range(1,n+1)]))
else:
dp[i][j][k] = float("inf")
ans = float('inf')
for j in range(1,n+1):
ans = min(ans, dp[m][j][t])
return ans if ans<float('inf') else -1
for _ in range(int(input())):
m,n,k = [int(i) for i in input().split()]
buildings = [int(i) for i in input().split()]
cost = [[int(i) for i in input().split()] for j in range(m)]
print(minCost(buildings,cost,m,n,k))
```