Grid Value
You are given a grid of size N*M. There are two types of people, type ‘A’ and type ‘B’ . You are also given the number of people of each type say ‘countA’ is the number of ‘A’ type persons and ‘countB’ is the number of ‘B’ type of persons. The satisfaction of a particular type of person can increase or decrease as follows :

The initial satisfaction of a person of type A is 80. It decreases by 20 for each neighbor. The initial satisfaction of a person of type B is 50. It increases by 10 for each neighbor.

Your task is to determine the maximum possible grid satisfaction.

Note:

You may choose exactly how many people you want to be present in the grid. The total number of people of type ‘A’ living in the grid can be less than ‘countA’ but cannot exceed ‘countA’. Similarly, total number of people of type ‘B’ living in the grid can be less than ‘countB’ but cannot exceed ‘countB’ A person can live in only one cell. Not more than one person can live in a cell. Two cells are said to be neighbors if the cells are adjacent and share a boundary.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the ‘T’ test cases follow. The first and the only line of each test case contains four space-separated integers ‘N’, ‘M’, ‘countA’, and ‘countB’, denoting the grid’s dimensions and the number of each type of people present.

Output Format:

For each test case, print in a new line an integer denoting the maximum possible grid satisfaction.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1

Question

Grid Value

You are given a grid of size N*M. There are two types of people, type ‘A’ and type ‘B’ . You are also given the number of people of each type say ‘countA’ is the number of ‘A’ type persons and ‘countB’ is the number of ‘B’ type of persons. The satisfaction of a particular type of person can increase or decrease as follows :

The initial satisfaction of a person of type A is 80. It decreases by 20 for each neighbor.

The initial satisfaction of a person of type B is 50. It increases by 10 for each neighbor.

Your task is to determine the maximum possible grid satisfaction.

Note:

You may choose exactly how many people you want to be present in the grid.

The total number of people of type ‘A’ living in the grid can be less than ‘countA’ but cannot exceed ‘countA’. Similarly, total number of people of type ‘B’ living in the grid can be less than ‘countB’ but cannot exceed ‘countB’

A person can live in only one cell.

Not more than one person can live in a cell.

Two cells are said to be neighbors if the cells are adjacent and share a boundary.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run.  Then, the ‘T’ test cases follow. 

The first and the only line of each test case contains four space-separated integers ‘N’, ‘M’, ‘countA’, and ‘countB’, denoting the grid’s dimensions and the number of each type of people present.

Output Format:

For each test case, print in a new line an integer denoting the maximum possible grid satisfaction.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 2
1 <= N,M <= 6
0 <= countA, countB <= min(N*M, 6)

Time Limit: 1sec

Accepted Answer

Using Recursion

The approach is to use Recursion along with Bitmasking. We can observe that we only need to know the last M cells we processed. We should only consider the cells at the top and left of the current cell because the right direction will be covered by someone else's left position, and the bottom position will be covered by someone else's top position. If a cell is filled, its contribution is fixed. If a neighbor cell is filled later, then the contribution of the original cell can be calculated towards the neighbor cell only.

Steps

Initialize two variables to maintain bitmasks for each type of person. Let’s call them mask_A=0 and mask_B=0.
Now, return the value of the recursive function, findMaxValue(m,n,countA,countB,mask_A, mask_B).

int findMaxValue(m,n,curr_pos,countA_remaining,countB_reamining,mask_A, mask_B)

Find the location of the current cell. row = curr_pos/n and col = curr_pos%n.
If row >= m, return 0.
Now, define n_mask_A = (mask_A << 1) & 63 and n_mask_B = (mask_B << 1) & 63.
Now, define maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B). maxValue is now equal to the value we get if the current cell is left empty.
If countA_remaining>0,
1. Define placingA_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
2. Update maxValue = max(maxValue, placingA_cost + findMaxValue(m,n,curr_pos+1,countA_remaining-1, countB_remaining,n_mask_A+1,n_mask_B)
If countB_remaining>0,
1. Define placingB_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
2. Update maxValue = max(maxValue, placingB_cost + findMaxValue(m,n,curr_pos+1,countA_remaining, countB_remaining-1,n_mask_A,n_mask_B+1)
Return the value of maxValue.

int neighborCost( m, n, row, col, mask_A, mask_B, diff)

Initialize cost = 0
Define top = 1 << (n-1)
If col > 0 and mask_A & 1, add diff-20 to cost.
If row > 0 and mask_A & top, add diff-20 to cost.
If col > 0 and mask_B & 1, add diff+10 to cost.
If row > 0 and mask_B & top, add diff+10 to cost.
Return cost.

Space Complexity: OtherExplanation:

O(3 ^ (M*N)), where M and N are the dimensions of the grid.

Time Complexity: OtherExplanation:

O(3 ^ (M*N)), where M and N are the dimensions of the grid.

Accepted Answer

Dynamic Programming with Bitmasking

The approach is to use Dynamic Programming along with Bitmasking. We can observe that we only need to know the last M cells we processed. We should only consider the cells at the top and left of the current cell because the right direction will be covered by someone else's left position, and the bottom position will be covered by someone else's top position. If a cell is filled, its contribution is fixed. If a neighbor cell is filled later, then the contribution of the original cell can be calculated towards the neighbor cell only. We can optimize our solution by storing the values for smaller subproblems in an array so that we don’t require to calculate the answer for the same subproblems again.

Steps

Initialize two variables to maintain bitmasks for each type of person. Let’s call them mask_A=0 and mask_B=0.
Now, return the value of the recursive function, findMaxValue(m,n,,countA,countB,mask_A, mask_B).

int findMaxValue(m,n,curr_pos,countA_remaining,countB_reamining,mask_A, mask_B)

Find the location of the current cell. row = curr_pos/n and col = curr_pos%n.
If row >= m, return 0.
Now, if the value at memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] has been stored already, then return this value after subtracting 1 from it. We are subtracting 1 here because while storing the value, we are adding 1 to it.
Now, define n_mask_A = (mask_A << 1) & 63 and n_mask_B = (mask_B << 1) & 63.
Now, define maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B). maxValue is now equal to the value we get if the current cell is left empty.
If countA_remaining>0,
1. Define placingA_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
2. Update maxValue = max(maxValue, placingA_cost + findMaxValue(m,n,curr_pos+1,countA_remaining-1, countB_remaining,n_mask_A+1,n_mask_B)
If countB_remaining>0,
1. Define placingB_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
2. Update maxValue = max(maxValue, placingB_cost + findMaxValue(m,n,curr_pos+1,countA_remaining, countB_remaining-1,n_mask_A,n_mask_B+1)
Now, make memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] = maxValue + 1.
Return the value of maxValue.

int neighborCost( m, n, row, col, mask_A, mask_B, diff)

Initialize cost = 0
Define top = 1 << (n-1)
If col > 0 and mask_A & 1, add diff-20 to cost.
If row > 0 and mask_A & top, add diff-20 to cost.
If col > 0 and mask_B & 1, add diff+10 to cost.
If row > 0 and mask_B & top, add diff+10 to cost.
Return cost.

Space Complexity: OtherExplanation:

O( (M*N) * (countA*countB) * (2^countA) * (2^countB) ), where M and N are the dimensions of the grid and countA and countB are the counts of the people of each type.

Time Complexity: OtherExplanation:

O( (M*N) * (countA) * (countB) ), where M and N are the dimensions of the grid and countA and countB are the counts of the people of each type.

Java (SE 1.8)

/*

    Time Complexity: O((M*N)*(countA)*(countB))

    Space Complexity: O( (M*N) * (countA*countB) * (2^countA) * (2^countB) ),



    Where M and N are the dimensions of the grid and countA and countB are the number of people of each type.

*/



public class Solution 

{



    // Define a dp table to store the answers for all dp states.

    public static int memo[][][][][] = new int[25][7][7][64][64];

    

    public static int neighborCost(int m, int n, int row, int col, int mask_A, int mask_B, int diff) 

    {



        int cost = 0;

        int top = (1 << (n - 1));



        if (col > 0 && (mask_A & 1) != 0) 

        {

            cost += diff - 20;

        }



        if (row > 0 && (mask_A & top) != 0) 

        {

            cost += diff - 20;

        }



        if (col > 0 && (mask_B & 1) != 0) 

        {

            cost += diff + 10;

        }



        if (row > 0 && (mask_B & top) != 0) 

        {

            cost += diff + 10;

        }



        return cost;

    }



    

    public static int findMaxValue(int m, int n, int curr_pos, int countA_remaining, int countB_remaining, int mask_A, int mask_B) 

    {



        // Find out the position of the current cell.

        int row = curr_pos / n;

        int col = curr_pos % n;



        if (row >= m) 

        {

            return 0;

        }



        // If the value corresponding to the current parameters has already been calculated, 

        // return the value by subtracting 1 from it, as we added 1 previously.

        if (memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] != 0) 

        {

            return memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] - 1;

        }



        // Update the values of masks for both type.

        int n_mask_A = (mask_A << 1) & 63;



        int n_mask_B = (mask_B << 1) & 63;



        // The satisfaction if the current cell is not filled.

        int maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B);



        if (countA_remaining > 0)

        {

            // The satisfaction if A is placed in the current cell.

            int placingA_cost = 80 + neighborCost(m, n, row, col, mask_A, mask_B, -20);



            // Upadte the maximum possible satisfaction

            maxValue = Math.max(maxValue, placingA_cost + findMaxValue(m, n, curr_pos + 1, countA_remaining - 1, countB_remaining, n_mask_A + 1, n_mask_B));

        }



        if (countB_remaining > 0) 

        {

            // The satisfaction if B is placed in the current cell.

            int placingB_cost = 50 + neighborCost(m, n, row, col, mask_A, mask_B, 10);



            // Upadte the maximum possible satisfaction

            maxValue = Math.max(maxValue, placingB_cost + findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining - 1, n_mask_A, n_mask_B + 1));

        }



        // Store the maximum satisfaction by adding 1 to it.

        memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] = maxValue + 1;



        // Return the maximum possible satisfaction.

        return maxValue;

    }



    

	public static int maxGridValue(int m, int n, int countA, int countB) 

    {

		// Initilaize the mask values for each type.

        int mask_A = 0, mask_B = 0;



        return findMaxValue(m, n, 0, countA, countB, mask_A, mask_B);

	}

}

Python (3.5)

'''

    Time Complexity: O(M*N*countA*countB)

    Space Complexity: O( (M*N) * (countA*countB) (2^countA) (2^countB) ),



    Where M and N are the dimensions of the grid and countA and countB are the number of people of each type.

'''



# Define a memo table to store the answers for all dp states.

memo = [[[[[0 for i in range(64)] for j in range(64)] for k in range(7)] for l in range(7)] for m in range(25)] 



def neighborCost(m, n, row, col, mask_A, mask_B, diff):

	cost = 0

	top = (1 << (n - 1))



	if (col > 0 and (mask_A & 1)):

		cost += diff - 20



	if (row > 0 and (mask_A & top)):

		cost += diff - 20



	if (col > 0 and (mask_B & 1)):

		cost += diff + 10



	if (row > 0 and (mask_B & top)):

		cost += diff + 10;



	return cost





def findMaxValue(m, n, curr_pos, countA_remaining, countB_remaining, mask_A, mask_B):

	# Find out the position of the current cell.

	row = curr_pos // n

	col = curr_pos % n



	if (row >= m):

		return 0



	# If the satisfaction corresponding to the current parameters has already been calculated, 

	# return the satisfaction by subtracting 1 from it, as we added 1 previously.

	if (memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B]):

		return memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] - 1



	# Update the satisfactions of masks for both type.

	n_mask_A = (mask_A << 1) & 63

	n_mask_B = (mask_B << 1) & 63



	# The satisfaction if the current cell is not filled.

	maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B)



	if (countA_remaining > 0) :

		# The cost if A is placed in the current cell.

		placingA_cost = 80 + neighborCost(m, n, row, col, mask_A, mask_B, -20)



		# Upadte the maximum possible satisfaction

		maxValue = max(maxValue, placingA_cost + findMaxValue(m, n, curr_pos + 1, countA_remaining - 1, countB_remaining, n_mask_A + 1, n_mask_B))

	

	if (countB_remaining > 0):

		# The cost if A is placed in the current cell.

		placingB_cost = 50 + neighborCost(m, n, row, col, mask_A, mask_B, 10)



		# Upadte the maximum possible satisfaction

		maxValue = max(maxValue, placingB_cost + findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining - 1, n_mask_A, n_mask_B + 1))



	# Store the maximum satisfaction by adding 1 to it.

	memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] = maxValue + 1



	# Return the maximum possible satisfaction.

	return maxValue



def maxGridValue(m, n, countA, countB):



	# Initilaize the mask satisfactions for each type.

	mask_A = 0

	mask_B = 0

	return findMaxValue(m, n, 0, countA, countB, mask_A, mask_B)

C++ (g++ 5.4)

/*

    Time Complexity: O((M*N)*(countA)*(countB))

    Space Complexity: O( (M*N) * (countA*countB) * (2^countA) * (2^countB) ),



    Where M and N are the dimensions of the grid and countA and countB are the number of people of each type.

*/



// Define a dp table to store the answers for all dp states.

int memo[25][7][7][64][64] = {};



int neighborCost(int m, int n, int row, int col, int mask_A, int mask_B, int diff) {



	int cost = 0;

	int top = (1 << (n - 1));



	if (col > 0 && (mask_A & 1)) {

		cost += diff - 20;

	}



	if (row > 0 && (mask_A & top)) {

		cost += diff - 20;

	}



	if (col > 0 && (mask_B & 1)) {

		cost += diff + 10;

	}



	if (row > 0 && (mask_B & top)) {

		cost += diff + 10;

	}



	return cost;

}





int findMaxValue(int m, int n, int curr_pos, int countA_remaining, int countB_remaining, int mask_A, int mask_B) {



	// Find out the position of the current cell.

	int row = curr_pos / n;

	int col = curr_pos % n;



	if (row >= m) {

		return 0;

	}



	// If the value corresponding to the current parameters has already been calculated, 

	// return the value by subtracting 1 from it, as we added 1 previously.

	if (memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B]) {

		return memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] - 1;

	}



	// Update the values of masks for both type.

	int n_mask_A = (mask_A << 1) & 63;



	int n_mask_B = (mask_B << 1) & 63;



	// The satisfaction if the current cell is not filled.

	int maxValue = findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining, n_mask_A, n_mask_B);



	if (countA_remaining > 0) {

		// The satisfaction if A is placed in the current cell.

		int placingA_cost = 80 + neighborCost(m, n, row, col, mask_A, mask_B, -20);



		// Upadte the maximum possible satisfaction

		maxValue = max(maxValue, placingA_cost + findMaxValue(m, n, curr_pos + 1, countA_remaining - 1, countB_remaining, n_mask_A + 1, n_mask_B));

	}



	if (countB_remaining > 0) {

		// The satisfaction if B is placed in the current cell.

		int placingB_cost = 50 + neighborCost(m, n, row, col, mask_A, mask_B, 10);



		// Upadte the maximum possible satisfaction

		maxValue = max(maxValue, placingB_cost + findMaxValue(m, n, curr_pos + 1, countA_remaining, countB_remaining - 1, n_mask_A, n_mask_B + 1));

	}



	// Store the maximum satisfaction by adding 1 to it.

	memo[curr_pos][countA_remaining][countB_remaining][mask_A][mask_B] = maxValue + 1;



	// Return the maximum possible satisfaction.

	return maxValue;

}





int maxGridValue(int m, int n, int countA, int countB) {



	// Initilaize the mask values for each type.

	int mask_A = 0, mask_B = 0;



	return findMaxValue(m, n, 0, countA, countB, mask_A, mask_B);

}

Your task is to determine the maximum possible grid satisfaction.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Intuit Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern