Friday, April 4, 2002
Problem Summary
This was a fun problem set. It had dynamic programming and memoization, with a small amount of graph theory
thrown in. The easy problem was straightforward dynamic programming, the medium involved determining
whether two small graphs were isomorphic, while the hard involved exploiting memoization to reduce
the amount of time required to simulate all the possibilities.
ZigZag
Used as: Level 1:
Value |
300 |
Submission Rate |
4/4 (100%) |
Success Rate |
3/4 (75%) |
High Score |
sjelkjd for 281.30 points |
The solution to this problem is a somewhat obvious application of dynamic programming. Suppose for each
position in the sequence, we know the length of the longest subsequence of the sequence that starts at
that position where the first difference is positive, as well as the length of the same where the first
difference is negative. Then it is easy to insert a value at the beginning of the sequence and solve the
same problem for a sequence starting with this new value, using the information we already know.
Initially, we know the solution for the last pair of values in the sequence. The length of the longest
subsequence where the difference is either positive or negative will be 2 (while for the other sign it
will be 0). We then work backwards from the third to last value in the sequence.
For each value, we determine the maximum subsequence length we'd get if we skip the values between the
current value and each following value. Depending on whether the difference between the current value and
the value we're skipping to is positive or negative, we look at the appropriate maximum length for
subsequences starting at the value we're skipping to and add 1. Once we try skipping to all values
following our current value, we can take the maximum for each sign.
Once we work all the way to the beginning of the sequence, we then look over all signs for all values,
pick the maximum value and return it.
Criminal
Used as: Level 2:
Value |
550 |
Submission Rate |
3/4 (75%) |
Success Rate |
3/3 (100%) |
High Score |
bstanescu for 423.90 points |
This problem is basically a graph isomorphism problem. We begin by building two graphs, one for the
database and one for the field data. This is straight forward, as each element in these input arrays
describes an edge in the resulting graph. We then have to determine whether or not these graphs are
isomorphic, and, if so, determine the maximum possible number of aliases.
Since we're limited to 8 vertices in each graph, we can use a crude approach. First, of course,
we should verify that the two graphs have the same number of vertices (else they cannot be isomorphic).
Then, we fix the ordering of the vertices of one graph and permute through each possible ordering of
vertices of the second graph. For each possible ordering, we can compare respective vertices from both
graphs and see if they both have the same number of edges all going to the same vertices. If so, then
we have found one way in which the two graphs can be said to be isomorphic.
Since it's possible that multiple orderings of the vertices of the second graph could yield the same
configuration as the first graph, we must iterate through them all. For each one that yields the same
configuration, we must count the number of aliases. This is just a count of the number of respective
vertices that have different labels. We store the maximum number of aliases and return it when we have
iterated through all orderings.
TimeSlicing
Used as: Level 3:
Value |
1000 |
Submission Rate |
3/4 (75%) |
Success Rate |
3/3 (100%) |
High Score |
sjelkjd for 874.63 points |
If you visualize all the possible ways to schedule two processes, you'll see that each schedule is a
path through a directed acyclic graph (DAG). Each vertex of this graph represents a state, consisting
of how long each process has waited in combination with how much time each process has accrued.
Much like the TicTacToe problem from last round, this is a memoization problem. We walk the graph as
we generate it, keeping track of vertices we have visited. Anytime we revisit a vertex, we already
know the number of successful paths we will obtain through this vertex, and so we will never simulate
duplicate suffixes of schedules.
The description of a state has 4 parts, so we will have a 4-dimensional array. The indices into this
array will be the components of the state: current wait time for process A; current wait time for process
B; time accrued by process A; and time accrued by process B. Since A gets the first slice, our initial
state is (0, 1, 1, 0). We call our recursive function with these parameters, and it will give us the answer.
The first thing this recursive function does is check the memoization table, to see if an answer for the
given input parameters has already been computed. If so, it returns it. Otherwise it will have to compute
it. To compute it, we first determine if the state is valid or not. It is invalid if any of the components
of the state exceed their maximum values (too much time waiting or too much time accrued). If this is the
case, the function returns 0. Next, we determine if the state is a final, successful state or not. This is
any valid state where the accrued time for both processes is the number of time slices needed by each. If
this is the case, we return 1.
Otherwise, we must traverse all the edges from this current state. There can be at most two, one
representing A being scheduled next, the other representing B being scheduled next. We recursively
call the function on the two possible states derived from the current state, and return the sum of
the return values.
By Logan
TopCoder Member
|