TopCoder problem "BaronsAndCoins" used in SRM 451 (Division I Level Two)



Problem Statement

    The game "Barons and Coins" utilizes a customized chess board that can be much larger than the usual 8x8. The game involves the use of a special chess piece, the baron. Initially, a baron is placed on the top-left cell of the board (specified as x=0, y=0) and coins are placed by the other players on specific cells of the board. The objective of the game is to use the baron to capture as many coins as possible. A coin is considered captured when the player moves the baron to the cell where the coin has been placed.



A baron's movement is as follows: In the first turn, the baron moves from its cell (x,y) to cell (x + K1, y + 1) such that K1 is positive. After the first turn, the i-th move is specified as moving from current cell (x,y) to a new cell (x+Ki , y+1) such that Ki is strictly greater than Ki-1 .



The coordinates of every coin are given in the int[] x and the int[] y, where the i-th coin is located on cell (x[i], y[i]). Return the maximum number of coins a player can capture.
 

Definition

    
Class:BaronsAndCoins
Method:getMaximum
Parameters:int[], int[]
Returns:int
Method signature:int getMaximum(int[] x, int[] y)
(be sure your method is public)
    
 

Constraints

-x will contain between 1 and 50 elements, inclusive.
-y will contain the same number of elements as x.
-Each element of x will be between 1 and 10000, inclusive.
-Each element of y will be between 1 and 10000, inclusive.
-Each pair x[i], y[i] will be distinct.
 

Examples

0)
    
{15, 5, 30}
{4, 5, 6}
Returns: 2
The baron can move in this order to obtain the coins at (15,4) and (30,6):

(0,0) -> (2,1) -> (5,2) -> (9,3) -> (15,4) -> (22,5) -> (30,6)
1)
    
{10}
{10}
Returns: 0
No valid sequence of baron movements can take the baron from (0,0) to (10,10).
2)
    
{1, 3, 6, 10, 15, 21}
{1, 2, 3, 4, 5, 6}
Returns: 6
3)
    
{5, 10, 15, 20, 25, 30, 35, 40, 45}
{1, 1, 1, 2, 2, 2, 3, 3, 3}
Returns: 3
4)
    
{1, 3, 6, 10, 22, 35, 50, 66}
{1, 2, 3, 1, 2, 3, 4, 5}
Returns: 5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13905&pm=10006

Writer:

vexorian

Testers:

PabloGilberto , bmerry , ivan_metelsky

Problem categories:

Dynamic Programming, Search