PROBLEM STATEMENT
You are taking ballroom dance lessons and currently you've learned five steps
from Rumba: BASIC, FAN, ALEMANA, HOCKEY STICK, BACKWARD WALKS. Each of the
steps can commence or end in one of three positions: closed position, open
position or fan position.
More precisely:
- BASIC step must commence in closed or open position and must end in closed or
open position (that is, all four different cases are possible)
- FAN must commence in closed position and must end in fan position
- ALEMANA must commence in fan or open position and must end in closed position
- HOCKEY STICK must commence in fan position and must end in open position
- BACKWARD WALKS must commence in open or closed position and must end in the
same position as the commencing position
You would like to create a Rumba routine for your first competition. You would
like to include all five steps you know. Also, in each routine, each step must
start in the position in which the previous step ended. There are no additional
restrictions for a position in which you commence your first step and with
which you end your last step.
Your task is, given a list of steps, to check if all five steps you've learned
are included and to check if it is possible to dance this combination of steps
in the order they appear in the list. More precisely, you should return two
integers: the first integer will indicate how many steps are missing. The
second integer will be equal to -1 if the combination can be danced together or
will be equal to the number of the first step that can't be danced (we start
counting steps from 1).
NOTE
The second number to return should be the step you can't dance even if you
tried every possibility for the starting position and used all possibilities
for the intermediate positions. For example, the routine {BASIC, ALEMANA} you
can dance, as you can choose to end BASIC in the open position which allows you
to commence ALEMANA; but in the routine {BASIC, HOCKEY STICK} you can't dance
HOCKEY STICK as you can end BASIC in the open or closed position and you must
commence HOCKEY STICK in the fan position.
DEFINITION
Class: Rumba
Method: routine
Parameters: String[]
Returns: int[]
Method signature (be sure your method is public): int[] routine(String[] steps);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- steps contains between 0 and 15 elements inclusive
- each element of steps is one of: "BASIC", "FAN", "ALEMANA", "HOCKEY STICK",
"BACKWARD WALKS"
EXAMPLES
1. steps = {"BASIC","FAN","HOCKEY STICK","BACKWARD WALKS","BASIC"} return
{1,-1} as ALEMANA is missing
2. steps = {"BASIC","FAN","HOCKEY STICK","BACKWARD WALKS","ALEMANA","BASIC"}
return {0,-1}
3. steps = {"BASIC","FAN","HOCKEY STICK","BACKWARD WALKS","BASIC","HOCKEY
STICK","ALEMANA"} return {0,6} as BASIC ends in open or closed position, but
HOCKEY STICK starts in fan position, thus, the last HOCKEY STICK can't commence
properly
4. steps = {} return {5,-1}
5. steps = {"ALEMANA","HOCKEY STICK"} return {3,2} as HOCKEY STICK can't be
danced after ALEMANA as ALEMANA ends in closed position and HOCKEY STICK can
start in fan position only
6. steps = {"ALEMANA","ALEMANA"} return {4,2} as ALEMANA ends in closed
position and commences in fan or open position, second ALEMANA can't be danced
7. steps = {"ALEMANA","BASIC","ALEMANA"} return {3,-1} as BASIC step gives us
the freedom to connect one ALEMANA to another, since we can commence the BASIC
step in closed position (which is the end of ALEMANA) and we can end the BASIC
in open position, which allows to start the second ALEMANA