TopCoder problem "Staircase" used in TCHS SRM 25 (Division I Level Three)



Problem Statement

    There is an ascending staircase where each step has a distinct absolute height above the floor given in inches. You must climb the staircase using a series of moves. On each move, you must do one of the following:
  • If the next step is 1 inch higher than your current step, you can go up to the next step.
  • If you are not on the first step, you can go down to the previous step.
  • If your K most recent moves have all been down, you can go up any number of steps, as long as you do not climb more than 2^K inches higher than your current step.


You are given a int[] stairs containing the heights of the steps from bottom to top. You are initially on the bottom step. Return the minimal number of moves necessary to reach the top step. Return -1 if it is impossible.
 

Definition

    
Class:Staircase
Method:minimalSteps
Parameters:int[]
Returns:int
Method signature:int minimalSteps(int[] stairs)
(be sure your method is public)
    
 

Constraints

-stairs will contain between 2 and 50 elements, inclusive.
-The first element of stairs will be 0.
-Elements of stairs will be in increasing order.
-Each element of stairs will be between 0 and 109, inclusive.
 

Examples

0)
    
{0,1,2,3,6}
Returns: 7
Go three steps up, then three steps down, then go to the last step.
1)
    
{0,1,2,4,8}
Returns: 9
Up two steps, down two steps, up to the step of height 4, down three steps, then to the last step.
2)
    
{0,2,3,4,5,6,7,8}
Returns: -1
You can't do the first move.
3)
    
{0,1,2,3,5,10,100}
Returns: -1
4)
    
{0,1,2,3,4,7,10,15,50,100,200,300,400,500,1000}
Returns: 36
5)
    
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
Returns: 13

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10077&pm=7241

Writer:

Vedensky

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming