MKCOM - Editorial

PROBLEM LINK:

Practice

Contest

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:

DP(i,j,k) = \left. \begin{cases} min[DP(i-1,j,k),min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\}], & \text{if} (\textbf{buildings}[i] = j \: \text{and} \: k \leq i)\\ \textbf{cost}[i][j]+min[DP(i-1,j,k),min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\}], & \text{if} (\textbf{buildings}[i] = 0 \: \text{and} \: k \leq i)\\ \infin, & \text{else} \end{cases} \right\}

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):

\;\;\;\;DP(i,j,k) = min[DP(i-1,j,k),min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\}]
  • 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):

\;\;\;\;DP(i,j,k) = \textbf{cost}[i][j]+ min[DP(i-1,j,k),min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\}]
  • 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:

DP(i,j,k) = \left. \begin{cases} min[DP(i-1,j,k),min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\}], & \text{if} (\textbf{buildings}[i] = j \: \text{and} \: k \leq i)\\ \textbf{cost}[i][j]+min[DP(i-1,j,k),min\{DP(i-1,p,k-1) \: \forall \: (1 \leq p \leq N, p \neq j)\}], & \text{if} (\textbf{buildings}[i] = 0 \: \text{and} \: k \leq i)\\ \infin, & \text{else} \end{cases} \right\}

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))
1 Like