Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?

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 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