Grid Satisfaction Problem

In this problem, you are given a grid of size N*M containing two types of people: type ‘A’ and type ‘B’. You are given the number of people of each type: 'countA' denotes the number of type 'A' people, and 'countB' denotes the number of type 'B' people. The satisfaction level of each type of person changes based on the number of neighbors they have:

  • Type A starts with an initial satisfaction of 80 and it decreases by 20 for each neighbor.
  • Type B starts with an initial satisfaction of 50 and it increases by 10 for each neighbor.

Your task is to determine the maximum possible grid satisfaction.

Example:

Input:
2
N = 2, M = 2, countA = 2, countB = 0
N = 3, M = 3, countA = 1, countB = 1
Output:
120
130

Explanation:

  • In the first test case, placing two type 'A' people optimally gives a satisfaction sum of 120.
  • In the second test case, placing one type 'A' and one type 'B' optimally gives a satisfaction sum of 130.

Constraints:

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

Note that you do not have to fill the entire grid. The number of people for each type can be less than the given 'countA' and 'countB' but cannot exceed them. A person occupies one cell and no cell can have more than one person. Neighbors are cells that are adjacent and share a boundary.

AnswerBot
2d

Given a grid with type A and B people, maximize satisfaction based on neighbors.

  • Start with type A people for maximum satisfaction

  • Optimally place people to maximize satisfaction

  • Consider satisfaction le...read more

Help your peers!
Add answer anonymously...
Intuit Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter