Friday, April 4, 2002
Problem Summary
These were easy problems, by semifinal standards. The easy problem, a
ReversePolishNotation calculator, is really just a measure of typing speed. The medium, a sort of TicTacToe
"AI", was relatively easy for a medium problem as well. The hard problem was nice and hard, however,
with a brief and elegant solution that is only apparent after some thinking.
RPN
Used as: Level 1:
Value 
200 
Submission Rate 
4/4 (100%) 
Success Rate 
4/4 (100%) 
High Score 
niteneb for 183.76 points 
This is a very easy problem for a semifinal round. All one needs is a working implementation of a stack, which any
language would come with. Or one could go without an explicit stack altogether, solving the problem recursively.
The process of evaluating an expression is fairly well described in the problem statement. We read the next token
(separated conveniently by spaces). If it is a digit, we push that value onto the stack. Otherwise, it is an
operation that we must apply to the top one or two elements of the stack.
Application of an operator is a simple switch statement (or something similar).
Not all of the operators are commutative (order is important for the  operator),
so it is important to make sure that operator is applied to the operands in the proper order.
When subtracting, the top of the stack is subtracted from the value just below it.
All that is left at this point is error checking. It is easy enough to ensure that the stack is empty at the end of
evaluation. It is marginally more difficult to make sure that the stack is nonempty every time a value is popped.
The whole evaluation process could simply be surrounded by an exception handler, or one can just be careful about
performing error checking at each point in the code where values from the stack are popped.
TicSolver
Used as: Level 2:
Value 
500 
Submission Rate 
4/4 (100%) 
Success Rate 
4/4 (100%) 
High Score 
dmwright for 364.04 points 
This simplest form of TicTacToe is generally liked by programmers, because it is such a small game.
There are only 3^{9} = 19683 possible ways to draw a TicTacToe board, and only a subset of those
possibilities represent valid game states. Because of this, it is easy to generate every possible outcome
from a given starting state.
The first piece of code we need is a function that determines whether a particular player has won. The crudest method
is hardcoding expressions that determine if every position in each winning triple of locations is occupied by the same player.
There are only eight of these triples. Once we have this function, we can work on board validity, as well as generating
possible outcomes.
There are two ways to determine board validity. The first consists of simply generating all possible states from the initial,
empty board, by following the rules of the game. If the input configuration isn't in this set of possible states, then
it must be invalid.
The other method is more analytical and easier to make a mistake with. First, count the number of Xs and the number of Os.
Since in this problem O goes first, the difference between the number of Os and the number of Xs must be either 0 or 1. Any
other difference indicates an invalid board. There are also a few other invalid conditions that involve a player having
already won. If the number of Os exceeds the number of Xs, but X has won the game, we have an invalid state.
If the number of Os equals the number of Xs, but O has won the game, we have an invalid state. If both players have won,
we also have an invalid state.
We are now ready to generate all the possible outcomes. These will be generated within a directed acyclic graph (DAG) structure.
Each particular state branches off into a number of possible new states, except for wins or draws which
form the vertices with no outgoing edges. For each state, we will need to know whose turn is next and whether or not they have won.
Once we have this DAG (or the means of generating it as we go along), we can implement a recursive function
that determines which player can force a win (if any) by walking the DAG.
The base case is when the next player can win on the next move or when all the locations are filled.
This corresponds to a vertex in the DAG with no outgoing edges.
Otherwise we look at every possible move for the current player. Our recursive function will tell us for
each move whether a win is forced or not. If there exists a move that forces a win for the current player,
then we know that the current state also means a forced win for the current player. Otherwise, the current
player has to hope for a way to force a draw. If a move exists that forces a draw, then the current state
also forces a draw. Otherwise, the other player can force a win from this particular state.
The DAG generation and the walk of the DAG can be implemented either separately and explicitly,
or together and implicitly. Implemented implicitly, the solution looks like standard memoization.
It helps to be able to generate a unique identifier for each state (e.g., a 9digit number in base3),
so that one can look up the result for a particular state in the memoization table. The return value
for our public method can then just involve a lookup of the input state in that table, after a check
for validity first.
TelephoneGame
Used as: Level 3:
Value 
1050 
Submission Rate 
2/4 (50%) 
Success Rate 
0/2 (0%) 
This is the sort of problem where the solution is difficult to derive, but once it is discovered, it
is very easy to implement. What makes this problem tractable is the fact that a circle of irremovable
connections is given. We know right off that a connection will have to be routed either within this circle or without.
For each pair of removable connections, we first determine whether they can exist on the same side of the
circle without crossing. Given two points along a circle, any third point on that circle will be between
those two points. If we arbitrarily pick one of the two given points, the third point will be located
in an interval that is either the clockwise or counterclockwise relative to the chosen point. This gives
us a simple means of labelling the two intervals.
To apply this model to this problem, let the two given points be the endpoints of one connection.
Then take a second connection. If and only if both endpoints of the
second connection are located in the same interval, then the connections do not cross.
For each pair of connections that cross, we know they must be routed on opposite sides of the circle. Suppose we
build a graph, where each vertex represents a connection, and an edge between two connections indicates that the
two connections cannot exist on the same side of the circle. Then it becomes evident that what we want to find the
largest subset of edges that make this a bipartite graph, meaning that the vertices can be grouped into two sets
consisting of vertices that have no edges to each other.
So all we have to do is build this graph, iterate through all subsets of edges in this graph, and choose the
subset with the most edges that gives a bipartite graph. To iterate through subsets of a set of
n elements, just count from
0 to 2^{n}  1. The binary representation of our counter will describe each subset.
For each subset, we have to determine whether it describes a bipartite graph. An alternate definition of
a bipartite graph is that it contains no cycles of odd length. Or, put another way, it means that we can
color all the edges using only two colors without having any two adjacent edges be the same color.
Whichever definition you choose to work with, it is fairly easy to implement a function that walks the graph
consisting of any given subset of edges and finds all the minimumlength cycles. If none exist that are of
odd length, we have a bipartite graph.
By Logan
TopCoder MemberAuthor Profile
