## Problem Statement | |||||||||||||

PROBLEM STATEMENT The Buddy System is applied to the children on a school outing. They are lined up in rows and columns (usually with a few adults to hold down the level of mayhem) and then are instructed to pair up with an adjacent child. Each pair of buddies must then hold hands during the outing. (No adult, of course, is anyone's buddy). We find that it works better when a pair is side-by-side in the same row, but if necessary we allow buddies to be front-to-back (adjacent in the same column). Create a class Buddy that contains the method pairUp that takes the number of rows and columns, n, and an int[] representing the locations of adults, adult, and returns the maximum number of side-by-side pairs that can be formed while making sure that each child is paired up with exactly one other child. If there is no way to pair up all the children, it will return -1. DEFINITION: Class: Buddy Method: pairUp Parameters: int, int[] Returns: int Method Signature (be sure your method is public): int pairUp(int n, int[] adult); There are n-squared people arranged in a square, with one corner being at row=1,col=1 and the diagonally opposite at row=n, col=n. adult contains row,col,row,col,... indicating the location of an adult with each row,col pair. Each other location in the square is occupied by a child. The same location may appear more than once in adult, in which case your program should ignore the redundant appearances. NOTES - no child may have more than one buddy TopCoder will ensure the validity of the inputs. Inputs are valid if all of the following criteria are met: - n is between 1 and 12 inclusive - adult contains between 0 and 50 elements inclusive - adult contains an even number of elements - each element in adult is between 1 and n inclusive EXAMPLES 1) n=4, adult = {1,1,4,4}: return -1. There are 14 children (4 x 4 - 2 adults). It is impossible to pair up all 14 with adjacent neighbors. 2) n=3, adult = {2,2,2,2,2,2}: return 2. x x y z A y z w w There is one adult in the center of the 3 x 3 square. We can pair the first 2 in row 1 and the last 2 in row 3 as side-by-side buddies, and the remaining 4 children can be paired as front-to-back buddies. This optimal pairing (there are others) is shown above. 3) n=12, adult = { }: return 72. All the children can be paired side-by-side. This is 12 x 12 children so 72 side-by-side pairs. 4) n=1, adult = {1,1}: return 0. There are no children, so they are already paired up! There are 0 side-by-side pairs. 5) n=12, adult = {12,12}: return -1 | |||||||||||||

## Definition | |||||||||||||

| |||||||||||||