#10618 - Tango Tango Insurrection

Solved By:wesley
Theory Difficulty:hard
Coding Difficulty:medium
Algorithms Used:dynamic programming
Solution Description: Our DP will be a series of arrays of size [4][4][3][70].

f(l, r, m, k) is the amount of energy it takes to complete the rest of dance given that you've completed k steps so far, your left foot is on square l, your right foot is on square r, and m is a value (0, 1, or 2) that represents which foot (if any) moved in the last step.

The convention I use for l and r is 0 = Up, 1 = Left, 2 = Right, 3 = Down.

For m I use 0 = no foot moved, 1 = Left, 2 = Right.

So, we want to determine f(1, 2, 0, 0), and return the appropriate sequence of actions. At each step, there are two cases:

Case 1: The next step is '.'

In this case, try moving your left foot to all four squares, and then try moving your right foot to all four squares. Nothing is going to be tapped, but you can use this pause in the music to reposition yourself. If you move a foot, make sure to output the foot that moved, even though it didn't tap.

Case 2: The next step is 'U', 'L', 'R' or 'D':

In this case, try moving your left foot to the appropriate square, and try moving your right foot to that square as well.

In both cases, make sure not to allow any illegal moves.

I recommend having three parallel arrays. Each is indexed as mentioned above, by (l, r, m, k). The first array, COST, is the standard DP array that keeps track of how much energy it takes to complete the dance from the given state. The second array, NEXT, keeps track of some integer or object that points to the next state in the path, and the third array, MOVE, keeps track of what move was taken.

For example, consider the input "LUR". We go through the following transitions to get the output "LRL":

l r m k

1 2 0 0 (move is "L")
1 2 1 1 (move is "R")
1 0 2 2 (move is "L")
2 0 1 3 (sequence is finished)

And the arrays look like this:

NEXT[1][2][0][0] = (1, 2, 1, 1)
MOVE[1][2][0][0] = 'L'
COST[1][2][0][0] = 3

NEXT[1][2][1][1] = (1, 0, 2, 2)
MOVE[1][2][1][1] = 'R'
COST[1][2][1][1] = 2

NEXT[1][0][2][2] = (2, 0, 1, 3)
MOVE[1][0][2][2] = 'L'
COST[1][0][2][2] = 1

At the end of the DP, use the information in NEXT to traverse through the optimal states, and use the information in MOVE to print out the move sequence.

Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By PHPGraphLib - Click For Official Site