Paint House IIl

Hard
0/120
8 upvotes
Asked in companies
AtlassianD.E.Shaw

Problem statement

The Ninjas of Ninjaland are very excited about their annual Ninja Festival, which is about to happen. So this time, they decided to paint their house such that exactly the ‘M’ neighbourhood group could be formed.

A Neighbourhood group is a continuous group of houses having the same color. For example, if the colors of house is [2,2,2,3,1,1,1]. There exist 3 neighbourhood groups [2,2,2], [3], [1,1,1].

You are given a 2-D array ‘COST’ where COST[i][j-1] denotes the cost for painting the i’th house with j’th color. There are ‘N’ houses and ‘K’ colours available for painting these houses.

You are given a ‘HOUSES’ array where ‘HOUSES[i]’ denotes the current colour of i’th house. If HOUSES[i] = 0, it means that the house is not coloured, so Ninja has to colour it. Otherwise, the already painted houses should not be painted again. Your task is to find the minimum cost for colouring these houses so that exactly ‘M’ neighbourhood groups can be formed if it is impossible to paint them in this manner, print -1.

For Example 
If the given ‘HOUSES’ array is [0,2,1,2,0] and ‘COST’ array is [ [1,7],[1,1],[1,1],[1,1],  [5,1] ] and ‘M’ = 3. 
 The minimum cost will be 7+1 =8. We will colour the first house with colour 2 and the last house with colour 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains three integers, 'N’,’K’, and ‘M’, denoting the number of houses, the number of colours available, and the number of neighbourhood groups, respectively.

The next line of each test case has ‘HOUSES’ array.

The next ‘N’ lines of each test case have ‘K’ values corresponding to the values of ‘COST[i]’ for all ‘K’ colours.
Output Format: 
For each test case, return an integer corresponding to the minimum cost possible or -1.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 100.
1 <= K <= 10
1 <= M <= N
0 <= COST[i][j] <= 1000

Time limit: 1 sec
Sample Input 1:
2
5 2 3
0 2 1 2 0
1 7
1 1 
1 1
1 1
5 1
3 2 2
0 1 0
4 5
5 4
6 1
Sample Output 1:
8
5
Explanation of sample input 1:
For the first test case,
We will color the first house with color 2 and the last house with color 2 .So the total cost will be  7+1. Houses array will look like [2,2,1,2,2], which has exactly 3 neighborhood groups. Hence the answer is 8. 

For the second test case:
We will color the first house with color 1 and the last house with color 2. So the total cost will be  4+1. Houses array will look like [1,1,2], which has exactly 2 neighborhood groups. Hence the answer is 5.
Sample Input 2:
2
4 2 3
2 1 2 0 
6 2 
9 1 
5 4 
4 4
5 1 1
1 0 1 1 0 
2 
8 
5   
1 
5
Sample Output 2:
4
13
Hint

Try to find the answer by trying out all ‘K’ colors for each unpainted building.

Approaches (3)
Recursion

In this approach, we will use a recursive function to find the minimum cost required. We will define a function HELPER(‘IDX’,’ TARGET’,’LAST_COLOR’,’ HOUSES’,’ COST’).IDX is the current index of ‘HOUSE,’ and ‘TARGET’ is the remaining number of neighborhood groups and ‘LAST_COLOR’ is the color of the last house. We will try each color for the houses which are not painted yet (‘HOUSES’[IDX] == 0).

 

Algorithm:

  • Defining HELPER(‘IDX’,’ TARGET’,’LAST_COLOR’,’ HOUSES’,’ COST’) function.
    • If ‘IDX’ == length of ‘HOUSES’ and ‘TARGET’ is equal to 0:
      • Return 0 . (All houses painted and groups is equal to ‘M’).
    • If ‘IDX’ >= length of ‘HOUSES’ OR ‘TARGET’ is less than 0:
      • Return INT_MAX (Conditions not satisfied).
    • If ‘HOUSES[‘IDX’], not equal 0:
      • The house is already painted.
      • If ‘HOUSES[‘IDX’] is not equal to LAST_COLOR’:
        • A new neighborhood group.
        • Set ‘TARGET’ as ‘TARGET’ -1.
      • Return  ‘HELPER(‘IDX’ + 1,’TARGET’,HOUSES[‘IDX’],’HOUSES’,’COST’).
    • Set ‘ANS’ as INT_MAX.
    • Trying each color for the uncolored house.
    • For each index i in range 1 to the size of ‘COST[‘IDX’]’, do the following:
      • If  i is equal to ‘LAST_COLOR’:
        • Set ‘NEW_TARGET’ as ‘TARGET’.
      • Else:
        • Set ‘NEW_TARGET’ as ‘TARGET’ -1 (A new neighborhood group.)
      • Set ‘ANS’ as the minimum of ‘ANS’ and COST[‘IDX’][i -1] + ‘HELPER(‘IDX’ + 1, ’NEW_TARGET’, i, ’HOUSES’, ’COST’).
    • Return ‘ANS’.

 

  • Set ‘ANS’ as ‘HELPER(‘0,’M’0,’HOUSES’,’ COST’).
  • If ‘ANS’ is ‘INT_MAX’.
    • Return -1. (Impossible to paint to fulfill the condition.)
  • Return ‘ANS’.
Time Complexity

O(K^(N*M)), where ‘N’ is the number of houses, ’K’ is the number of colors available, and ‘M’ is the target number of groups.

 

In this approach, in the worst case, we will run the 'HELPER' function for all pairs of {‘IDX’,’ TARGET’} and in each call, in the worst case, will we trying each color. There are a total of pairs are ‘N’*’M,’ and for each subarray, we are making K more calls for each call. So the total time is K^(N*M). Hence the overall time complexity is O(K^(N*M)).

Space Complexity

O( K^(N*M) ), where ‘N’ is the number of elements in 'ARR'.

 

In this approach, in the worst case, we are making K^(N*M) calls of 'HELPER'() function. Hence the overall space complexity is O( K^(N*M)).

Code Solution
(100% EXP penalty)
Paint House IIl
Full screen
Console