Grid Value

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
8 upvotes
Asked in companies
FacebookAdobeIntuit

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
3 1 0 1
Sample Output 1:
50
Explanation For Sample Input 1:

In this test case, we can have only one person of type B. Since, this person will have no neighbors, the satisfaction of this person will not change and we will get the maximum grid value of 50.
Sample Input 2:
1
2 2 1 2
Sample Output 2:
190
Hint

Think of a recursive solution

Approaches (2)
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

 

  1. Initialize two variables to maintain bitmasks for each type of person. Let’s call them mask_A=0 and mask_B=0.
  2. 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)

 

  1. Find the location of the current cell. row = curr_pos/n and col = curr_pos%n.
  2. If row >= m, return 0.
  3. Now, define n_mask_A = (mask_A << 1) & 63 and n_mask_B = (mask_B << 1) & 63.
  4. 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.
  5. 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)
  6. 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)
  7. Return the value of maxValue.

 

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

 

  1. Initialize cost = 0
  2. Define top = 1 << (n-1)
  3. If col > 0 and mask_A & 1, add diff-20 to cost.
  4. If row > 0 and mask_A & top, add diff-20 to cost.
  5. If col > 0 and mask_B & 1, add diff+10 to cost.
  6. If row > 0 and mask_B & top, add diff+10 to cost.
  7. Return cost.
Time Complexity

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

Space Complexity

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

Code Solution
(100% EXP penalty)
Grid Value
Full screen
Console