TopCoder problem "Coherence" used in TCCC '03 Int'l Regional (Division I Level Two)



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

0)
    
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.
1)
    
4
6
16
Returns: 4
 X X X X - -
 X X X X - -
 X X X X - -
 X X X X - -
2)
    
9
5
0
Returns: 0

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=1106

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4466&pm=1106

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Advanced Math