JOIN
 Match Editorial
 Room 1 Review Archive Rookie Review Discuss this match Problem Set Want to write a feature?
SRM 84
April 30, 2002

Match summary

Div 1 - 250 - ChatParser
There was nothing tricky about this problem. All you had to do was scan the string, and remove the patterns as necessary. There were a few approaches to this. The most common was probably to scan the string from left to right, and if an eye is found, then check the next characters to see they match a face. If they do, then just remove it and check again from the same position. The highest scoring approach was that of SnapDragon.

Div 1 - 600 - VirtualMachine
This problem was pretty simple, in that it didn't require knowledge of any particular algorithms. However, it was a bit of code, and there were some opportunities to make mistakes. The basic approach is simple, you just have a loop that increments your PC at each iteration and in the loop you have a bunch of else-if statements to perform all of the various operations. There were a couple special cases that you have to handle - overflow and memory access out of bounds - but these were simple to check. All in all it was a pretty easy problem, and all that it took was care and time. See NDBronson's solution for the fastest submission of this problem.

Div 1 - 900 - FillRate
If the image is valid (the return is not -1) then it is very simple to find the minimum number of pixels required. For each color that is in the picture, you find the smallest rectangle such that all of the pixels of that color are within the rectangle (the bounding rectangle for that color). The minimum number of pixels is then simply the sum of the areas of all these rectangles.

In order to determine if a rectangle is valid, you need to check two things. The first is that there are no empty ('.') pixels within any of the bounding rectangles. The second is that there are no sets of colors where A is on top of B is on top of C is on top of A. Determining this is exactly analogous to finding loops in a graph. Directed edges in the graph are constructed from every color to every other color that it must be on top of (have at least one pixel within a particular color's bounding rectangle). Once all of the edges are constructed, there are a number of ways to find loops. The fastest to code is probably the a variant of the Floyd-Warshall algorithm (see John Dethridge's solution for an example). If a path is found from a pixel to itself, then there is a loop in the graph, and hence the picture is not valid.

 Problem Points Submission Rate Submission Succ. Avg. Pts. High Score Division I Level 1ChatParser 250 58.44% 96.28% 212.39 SnapDragon243.74 Level 2Virtual Machine 600 52.67% 21.81% 270.34 NDBronson372.67 Level 3FillRate 900 36.21% 25.93% 541.14 John Dethridge769.06 Division II Level 1LitLCD 250 92.56% 72.33% 207.37 androm247.02 Level 2ColorMatch 600 76.51% 54.41% 379.10 GroZZler556.91 Level 3ChatParser 900 65.58% 26.05% 619.11 LehooZeher851.45

By lbackstrom
TopCoder Member