BallRemoval

TCO12 Semifinal 2 · 2012-03-27 · by ir5

TCO12 Semifinal 2 · 2012-03-27 · by ir5 · Dynamic Programming

Show categories

Class Name: BallRemoval

Return Type: String

Method Name: canLeave

Arg Types: (string)

Problem Statement

You have N balls, where N is odd. The balls are numbered from 0 to N-1. In that order, they are arranged into a row going from the left to the right.

In addition to the number, each ball has either the word "left" or the word "right" written on it. For simplicity, we will use the character '<' instead of "left", and the character '>' instead of "right". You are given the labels on all balls as the String label. For each i, character i of label represents the word on ball i.

You will now repeat the following procedure:

Choose a ball that is not at either end of the row of balls.
If the chosen ball has the label '<', remove the chosen ball and also the ball immediately to the left of it. Otherwise, remove the chosen ball and also the ball to the right of it.
Without reordering the remaining balls, push them together to get rid of the gap created in the previous step.

The process ends when only one ball remains in the row. That ball is called the survivor. Note that the numbers on the balls do not change during the process.

Find all possible survivors. Your method must return a String containing exactly N characters. If ball i can be the survivor, character i of the return value must be 'o' (lowercase oh). Otherwise, the corresponding character must be '.' (a period).

Constraints

label will contain between 3 and 49 characters, inclusive.
label will contain an odd number of characters.
Each character of label will be either '>' or '<'.

Examples

"<<>"
Returns: "..o"

Initially, you have three balls. Since you cannot choose balls at the ends of the row, you have to choose ball 1. As its label is '<', you remove balls 0 and 1. Hence the only possible survivor is ball 2.

">>><<"
Returns: "o...o"

If you choose ball 2 or ball 3 first, you have to choose ball 1 next, and the survivor will be ball 0. If you choose ball 1 first, you have to choose ball 3 next, and the survivor will be ball 4.

"<<><<"
Returns: "....o"

"<><<><>"
Returns: "o.....o"

">>><<<>>>>><<<>"
Returns: "o.....o.o.....o"

Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BallRemoval with a public method string canLeave(string label) · 63 test cases · 2 s / 256 MB per case