Coherence

TCCC '03 Int'l Regional · 2003-02-22 · by dgoodman

TCCC '03 Int'l Regional · 2003-02-22 · by dgoodman · Advanced Math

Show categories

Class Name: Coherence

Return Type: int

Method Name: minBndry

Arg Types: (int, int, int)

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.

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

29
3
87
Returns: 0

28
22
145
Returns: 23

Submissions are judged against all 31 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Coherence with a public method int minBndry(int numRows, int numCols, int k) · 31 test cases · 2 s / 256 MB per case