TopCoder problem "CheapestRoute" used in SRM 407 (Division II Level Three)



Problem Statement

    There is a long corridor which consists of a single horizontal row of n cells, numbered 0 to n-1 from left to right. You are standing in the leftmost cell and you want to move to the rightmost cell. From each cell, you can walk left or right to an adjacent cell. It costs cellPrice[i] to walk into cell i. If the price of a cell is -1, you cannot walk into it.

Some cells may also contain teleports. The i-th teleport is located in cell enterCell[i], and when you use that teleport, it will take you to cell exitCell[i]. It costs teleportPrice+x to use a teleport, where x is the number of teleports you have used previously. When you enter a cell i using a teleport, you do not have to pay cellPrice[i] - you only pay the teleport price. However, if the price of a cell is -1, you cannot enter that cell using a teleport.

Determine the minimal total cost C required to reach the rightmost cell. Then, determine the minimum number of moves M required to reach the rightmost cell using that minimal cost C. Walking to an adjacent cell counts as a single move, and using a teleport counts as a single move. Return a int[] containing exactly two elements. The first element should be C and the second element should be M. If it is impossible to reach the rightmost cell, return an empty int[] instead.
 

Definition

    
Class:CheapestRoute
Method:routePrice
Parameters:int[], int[], int[], int
Returns:int[]
Method signature:int[] routePrice(int[] cellPrice, int[] enterCell, int[] exitCell, int teleportPrice)
(be sure your method is public)
    
 

Constraints

-cellPrice will contain between 1 and 50 elements, inclusive.

-enterCell will contain between 0 and 50 elements, inclusive.

-enterCell and exitCell will contain the same number of elements.

-Each element of cellPrice will be between -1 and 1000, inclusive.

-The first element of cellPrice will be between 0 and 1000, inclusive.

-teleportPrice will be between 0 and 1000, inclusive.

-Each element of enterCell and exitCell will be between 0 and n-1, inclusive, where n is the number of elements in cellPrice.

 

Examples

0)
    
{100}
{0}
{0}
1000
Returns: {0, 0 }
Here there is only one cell.
1)
    
{0,-1,0,0}
{0}
{2}
1000
Returns: {1000, 2 }
First, we use the teleport from cell 0 to cell 2. Then we walk from cell 2 to cell 3. Total cost is 1000+0+0=1000.
2)
    
{1,2,3}
{}
{}
100
Returns: {5, 2 }
There are no teleports, so we just walk from cell 0 to cell 1 and then to cell 2.
3)
    
{1,0,-1}
{0}
{2}
0
Returns: { }
The last cell is blocked, so we can't enter there.
4)
    
{4,2,1,0,5,6,0,3,0}
{4,4,3,7,5,4,2,5,8,4}
{7,3,5,0,5,4,5,0,8,3}
8
Returns: {14, 6 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12179&pm=9794

Writer:

Gluk

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Dynamic Programming