Last Updated: 20 Mar, 2021
Grid Value
Moderate
Asked in companies
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
Approaches
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,
- Define placingA_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
- 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,
- Define placingB_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
- 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.
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,
- Define placingA_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
- 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,
- Define placingB_cost = 80 + neighborCost(m,n,row,col,mask_A, mask_B, -20)
- 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.