Match Editorial

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

The three hundred point problem was solved most easily by brute force. You simply check every possible tile, by checking all of the sub rectangles whose upper left corner is the same as the given input. You then tile the image, and make sure that it works. This can be done quite easily with 4 nested loops. The outer two are for tile size, and the inner two check that everything matches up by using a couple of modulus operators.

The 500 could be solved with simple recursion. You are given a 2-D array and have to find the number of groups, and the borders between the groups. To do this you keep a 2-D boolean array that corresponds to the input map. You start with some point, and the recursively visit each of the adjacent points that belongs to the same farmer and has not yet been visited. Eventually, all of the points in the group will be marked visited. Then you find another unvisited point and start from it. After every point has been visited, the number of signs needed is equal to the number of times you had to start the recursion. The number of units of fence can be easy computed by examining every pair of adjacent points, and if they are not equal, adding 1. This could be done simply in the recursion by adding a unit of fence whenever the algorithm hits an adjacent point that is not the same as the point is it on. (You have to divide this by 2 at the end, since you count each section twice.)

The 1100 was very similar to a previous problem on TopCoder and is related to the game nim. The trick to the way I solved this was to realize that groups of 3 periods can be removed without effecting the outcome. This is because if there are three periods to the left of an X, then either player can force that piece to be moved three spaces to the left. That is, if a player moves it 1 space to the left, the other player can move it two spaces, and other a player moves it 2 spaces to the left, the other player can move it one more space. With this insight, a memoized recursion should solve the problem with out to much difficulty. Simply remove all groups of three periods and the try every move. If in of them are winning, then this position is winning otherwise it is not. By caching the results, we avoid recomputing boards, and run time is not an issue. An alternative solution uses XOR and parity to compute the answer without any search. dmwright and bigg_nate both implemented a form of this solution.