Coherence | Topcoder Archive

Problem Statement

We want to display a two-color pattern on a rectangular array of pixels, with k of the pixels in the foreground color. We want to choose the pattern so that it minimizes the boundary between the foreground and the background.

The length of the boundary is the number of vertical and horizontal pixel edges that separate a foreground pixel from a background pixel. For example, this picture shows a rectangular array with three rows and six columns that has 5 foreground pixels (indicated by 'X'). The boundary in this case has length equal to 6: the upper left X is adjacent to 1 background pixel, the upper middle X is adjacent to 1, the rightmost X is adjacent to 3, the lower left X is adjacent to 0, and the lower right X is adjacent to 1.

   - - - - - -
   X X X - - -
   X X - - - -

Create a class Coherence that contains the method minBndry that takes three int inputs, numRows (the height of the array), numCols (the width of the array), and k (the number of foreground pixels), and returns the length of the minimum possible boundary.

Definition

Class:: Coherence
Method:: minBndry
Parameters:: int, int, int
Returns:: int
Method signature:: int minBndry(int numRows, int numCols, int k)
(be sure your method is public)

Constraints

numRows is between 1 and 30 inclusive
numCols is between 1 and 30 inclusive
k is between 0 and numRows*numCols inclusive

Examples

```
6
```
```
6
```
```
5
```
```
Returns: 5
```
X X X - - - X X - - - - - - - - - - - - - - - - - - - - - - - - - - - - The upper right foreground pixel has 2 boundary edges, the bottom right one has 2 boundary edges, and the bottom left one has 1 boundary edge.
```
4
```
```
6
```
```
16
```
```
Returns: 4
```
X X X X - - X X X X - - X X X X - - X X X X - -
```
9
```
```
5
```
```
0
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.