
Match Editorial 
SRM 80April 15, 2002
Match summary
Division 1 easy  Sketch:
Most of the easy problems are quite easy and SRM 80's
were no exception. You just had to keep a 2D array of
the states of every grid location and move around as
the input says. The only thing to watch for is bumping
into the edge, in which case you do nothing. See
ZorbaTHut's solution of this for an example.
Division 1 medium  Integrate:
This was one of the easier mediums, as far as they go.
After an easy parse, you simply integrate as
specified. After integrating all terms, you have to
add them up, which is simple addition of fractions that
we learned in grade school. If you didn't do this in a
way such that the sum stayed simplified, you could run
into overflow problems on ints. Also, some solutions
put the negative sign on the denominator instead of the
numerator, but they were in good company, as NDBronson
made the same mistake. See Garzahd's solution in Room
3 for a quick way to do this without a fraction class.
Division 1 hard  Simulate:
This problem was a little bit tricky. Simulating the
circuit was pretty straightforward. You just
recursively get the outputs of each component for the
state at time t, and use this to compute the state at
time t+1. However, in order to do this efficiently you
had to do 2 things. First you had to cache the results
of each component at a given time step so that you
didn't end up evaluating it over and over. If you
don't cache the results, then your solution will run in
time O(24^49) or so, worst case. The other thing that
you have to notice is that the states loop. Once you
get to a state that you have previously reached, you
know how many time steps it takes for the states to
loop, and then you can do some clever arithmetic to
figure out which state it ends up at. For example, the
2 bit binary counter looped through the states 00, 01,
10, 11. Thus its output at time t was t%4 in binary.
NDBronson's solution to this problem was by far the
fastest, giving him well over a 100 points more than
the nearest competitor.
Problem 
Points 
Submission Rate 
Submission Succ. 
Avg. Pts. 
High Score 

Division I 

Level 1  Sketch 
250 
95.27897% 
80.25751% 
185.33156 
ZorbaTHut 239.67 

Level 2  Integrate 
500 
78.11159% 
32.188843% 
302.54666 
Garzahd 446.88 

Level 3  Simulate 
1100 
16.738197%% 
3.4334764% 
540.5 
NDBronson 748.43 


Division II (check back for info) 
By
lbackstrom
TopCoder Member