TopCoder problem "ScoreDifference" used in SRM 328 (Division II Level Three)



Problem Statement

    This problem statement contains an image that may not display properly if viewed outside of the applet.

You play a game with your friend in which 16 square pieces are placed in a 4x4 grid on a board. Each piece has a distinct number between 1 and 16 written on it. A piece can be removed from the board if it is on an edge or if it can be dragged left, right, up or down through a path of unoccupied squares, until it leaves the board. When a piece is removed from the board, the square it occupied becomes unoccupied.

On the board below, all pieces can be removed from the board. For example, the selected piece can be dragged one square down, then one square left, and finally it can be removed from the board by dragging it down:

You take alternate turns removing pieces from the board until all of them are removed. The score of each player is calculated by summing the values of the pieces he has removed. Each player follows an optimal strategy that maximizes the difference between his score and his opponent's score. You are the first to move.

You will be given a String[] board. Each element of board contains four integers separated by single spaces. The jth integer in the ith element of board represents the number written on the piece in the ith row and jth column of the grid. Return the maximum possible score difference between you and your friend, assuming both of you play optimally.

 

Definition

    
Class:ScoreDifference
Method:maximize
Parameters:String[]
Returns:int
Method signature:int maximize(String[] board)
(be sure your method is public)
    
 

Constraints

-board will contain exactly 4 elements.
-Each element of board will contain exactly four positive integers, with no leading zeroes, separated by single spaces, and will contain no leading or trailing spaces.
-Each integer between 1 and 16 will appear exactly once in board.
 

Examples

0)
    
{"12 4 5 13", 
 "3 14 16 9",
 "11 6 15 8",
 "2 1 7 10"}
Returns: 2
It is not always best to remove the piece with the highest point value. On the first turn you can remove any piece except the four middle ones. The best option is to remove the piece in the upper right corner. Your friend will then choose the piece from the upper left corner. It is still not possible to remove the middle four pieces. You go on by removing the 11 point piece and the piece valued 6 can now be removed. Your friend will remove the piece in the bottom right corner. At this point you have an advantage of 2 points. The piece with the highest value that can now be removed is the 9 piece. If you remove this one, the remaining pieces will be removed in the order 16, 15, 14, 8, 7, 6, 5, 4, 3, 2, 1 and you will end up in a draw game. However, if you remove the 8 piece, the remaining pieces will be removed in the order 8, 15, 16, 14, 9, 7, 6, 5, 4, 3, 2, 1 and you will keep the 2 point advantage.
1)
    
{"15 16 11 12",
 "10 13 4 7",
 "1 2 8 6",
 "9 5 3 14"}
Returns: 6
2)
    
{"6 8 1 16",
 "10 15 9 3",
 "2 5 7 14",
 "13 12 11 4"}
Returns: 10
3)
    
{"9 8 3 1",
 "10 6 15 5",
 "12 7 4 11",
 "14 13 16 2"}
Returns: 16

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10008&pm=6854

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Dynamic Programming, Recursion, String Parsing