TopCoder problem "RectangleDivision" used in TCO04 Finals (Division I Level Two)



Problem Statement

    Consider an a by b rectangle, composed of a*b unit squares. Your task is to count the number of ways in which this rectangle can be divided into two contiguous sections, each consisting of 1 or more unit squares. Each section must contain at least 1 square on the edge of the rectangle. A section is contiguous if each square in the section is connected to each other square in the section via a path of horizontally or vertically adjacent squares that are all within the section.
 

Definition

    
Class:RectangleDivision
Method:count
Parameters:int, int
Returns:int
Method signature:int count(int a, int b)
(be sure your method is public)
    
 

Constraints

-a will be between 1 and 6, inclusive.
-b will be between 2 and 6, inclusive.
 

Examples

0)
    
1
3
Returns: 2
There are two different ways to split up this rectangle, where '#' represents one section, and '.' the other: 
##.

#..
1)
    
3
2
Returns: 15
Here are the 15 ways: 
#.   .#   ..   ..   #.   .#   ..   ..
..   ..   ..   ..   #.   .#   #.   .#
..   ..   #.   .#   ..   ..   #.   .#

##   ..   ##   ##   ##   ##   #.
..   ..   #.   .#   #.   .#   #.
..   ##   ##   ##   ..   ..   #.
2)
    
3
3
Returns: 52

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5886&pm=3074

Writer:

lars2520

Testers:

PabloGilberto , Yarin , vorthys

Problem categories:

Brute Force