|
Match Editorial |
 |
|
||||||||||||
| |||||||||||||
| MATCH EDITORIAL LINKS: | |||||||||||||
|
|||||||||||||
| |||||||||||||
April 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) | |||||
