## Problem statement

You’re in charge of teaching a classroom of students and in the next assessment, each student has the option to work either in pairs or alone. As it turns out, the students are seated in an M x N rectangular grid, and each student can work with up to one adjacent classmate -- a student in the center of the classroom has up to 4 choices of partners, while those at the corners have up to 2.

We assume that the productivity of each student (when working alone) is represented by a positive integer. When two adjacent students work as a pair, their combined productivity is equal to the product of their individual productivities. For example, if two adjacent students have productivities of 3 and 5 each, then their total productivity would be 8 when working separately, but 15 when working together as a pair. Students with productivity 1 always prefer to work alone and should never be placed in a pair.

Task: Given the productivity for each individual in the class (as a grid of positive integers), design an algorithm that computes the maximum total productivity achievable by pairing students in the class. Note that the total productivity consists of the summed productivities of all pairs and students working alone; note also that productivity scores should only be counted once per pairing, not once for each individual in the pairing.

## Solution

Based on a checker pattern, students can be divided into two groups: those on the white spots, and those on the black spots. Position (0, 0) is the first white spot; next position (0, 1) is the first black spot and so on, as illustrated in figure below.

(0, 0) | (0, 1) | (0, 2) |

(1, 0) | (1, 1) | (1, 2) |

(2, 0) | (2, 1) | (2, 2) |

Observation: students on the white spots can only pair with students on the black spots and vice versa.

The maximum productivity value is attained when we can pair all students up in a way that the sum of their productivity values is greatest. And this problem can be easily solved with min-cost bipartie matching algorithm such as Hungarian algorithm.

With the input below, I got **1859** as the answer. What do you get?

```
inp = [
'7 5 9 2 3 1 9 3 3 6 2 1 5 3 4',
'1 2 7 1 5 2 8 6 1 3 4 3 4 7 3',
'2 9 5 4 4 2 5 1 1 6 1 8 9 5 2',
'1 8 2 2 4 3 8 8 8 9 6 7 3 6 7',
'8 1 4 2 4 7 9 9 1 5 4 7 7 6 2',
'4 3 6 3 2 3 8 9 5 2 7 4 7 1 1',
'2 7 2 6 1 2 3 3 3 6 5 6 1 1 7',
'4 6 2 3 6 2 6 4 3 2 1 1 5 7 7',
'6 5 9 6 4 1 2 3 6 2 4 9 8 4 7',
'5 9 6 8 5 2 3 5 1 7 2 8 5 7 5',
]
```

## No comments:

## Post a Comment