
Match Editorial 
SRM 84April 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 elseif 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 FloydWarshall 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 1 ChatParser 
250 
58.44% 
96.28% 
212.39 
SnapDragon 243.74 

Level 2 Virtual Machine 
600 
52.67% 
21.81% 
270.34 
NDBronson 372.67 

Level 3 FillRate 
900 
36.21% 
25.93% 
541.14 
John Dethridge 769.06 


Division II 

Level 1 LitLCD 
250 
92.56% 
72.33% 
207.37 
androm 247.02 

Level 2 ColorMatch 
600 
76.51% 
54.41% 
379.10 
GroZZler 556.91 

Level 3 ChatParser 
900 
65.58% 
26.05% 
619.11 
LehooZeher 851.45 

By
lbackstrom
TopCoder Member