JOIN
 Match Editorial
 Room 1 Review Archive Rookie Review Discuss this match Problem Set Want to write a feature?
SRM 80
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 ZorbaTHut239.67 Level 2 - Integrate 500 78.11159% 32.188843% 302.54666 Garzahd446.88 Level 3 - Simulate 1100 16.738197%% 3.4334764% 540.5 NDBronson748.43 Division II (check back for info)

By lbackstrom
TopCoder Member