17. Dance Dance Revolution is a dance video game, first introduced in Japan by Konami in 1998. Players stand on a platform marked with four arrows, pointing forward, back, left, and right, arranged in a cross pattern. During play, the game plays a song and scrolls a sequence of n arrows (, , , or ) from the bottom to the top of the screen. At the precise moment each arrow reaches the top of the screen, the player must step on the corresponding arrow on the dance platform. (The arrows are timed so that you'll step with the beat of the song.) You are playing a variant of this game called "Vogue Vogue Revolution", where the goal is to play perfectly but move as little as possible. When an arrow reaches the top of the screen, if one of your feet is already on the AMIC PROGRAMMING correct arrow, you are awarded one style point for maintaining your current pose. If neither foot is on the right arrow, you must move one (and only one) foot from its current location to the correct arrow on the platform. If you ever step on the wrong arrow, or fail to step on the correct arrow, or move more than one foot at a time, or move either foot when you are already standing on the correct arrow, all your style points are taken away and you lose the game. How should you move your feet to maximize your total number of style points? For purposes of this problem, assume you always start with your left foot on and your right foot on , and that you've memorized the entire sequence of arrows. For example, if the sequence is . can earn 5 style points by moving your feet as shown below: you L R Begin! R R Style point! R L RL L Style point! RL RL RL Style point! Style point! R Style point! (a) Prove that for any sequence of n arrows, it is possible to earn at least n/4-1 style points. (b) Describe an efficient algorithm to find the maximum number of style points you can earn during a given VVR routine. The input to your algorithm is an array Arrow[1..n] containing the sequence of arrows. 133