Match Editorial

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

Algorithms:
PoemCode - 250
Like most 250's the algorithm was straightforward and there were not really any special cases to watch for. You simply have to remove the extra characters (',','.', and ' ') and then loop from 'a' to 'z' and keep a counter outside the loop. Whenever you hit the letter your loop is on, you set the corresponding spot in your return array to the value of the counter, and increment the counter. Look at any solution in Room 1 to see this in action. This was one of the easier easy problems in recent history, with only 8 out of 215 people not submitting correct solutions.

Pinball - 450
This problem was pretty straightforward, and in general unsuccessful solutions were due to oversights rather than algorithmic mistakes, of which there were many as evidenced by a 96% submission rate, but only a 52% success rate. The key points to remember were to reset everything between games, to not raise the multiplier above 5, and not to clear the score after a game until a new game starts. Other than that, it was just a matter of looping through all the characters in the input and performing the appropriate operations. See John Dethridge's solution for a good, short implementation.

CleanupCrew - 1050
No matter how many toys your opponent picks up, you can always pick up a number of toys such that there are k+1 less toys in that pile than there were in the pile before your opponents turn. This can easily be seen by noting that player A must first pick up k+1-n toys, for some n between 1 and k. Player B may then pick up n toys so that a total of k+1 toys have been picked up. If player B does not pick up n toys, but picks up m toys instead, then player A can pick up k+1-n-m or 2k+2-n-m toys (whichever one is between 1 and k). Thus either player can force the game to come down to the point where the sizes of the piles are all the input size modulo k + 1. At this point the problem can be solved easily with dynamic programming by working backwards (see dmwright's solution) or with memoized recursion (see NDBronson's solution). An even simpler but much less obvious solution is malpt's. For a discussion of why this works go to http://www.cut-the-knot.com/nim_theory.shtml

Problem	Points	Submission Rate	Submission Succ.	Avg. Pts.	High Score
Division I
Level 1 PoemCode	250	99.07%	96.28%	221	NDBronson 244.20
Level 2 Pinball	450	95.81%	51.63%	326	Logan 412.42
Level 3 CleaupCrew	1050	30.23%	11.16%	631	thekcc 981.45
Division II
Level 1 Scoreboard	250	97.65%	97.07%	240	kokon 249.16
Level 2 PoemCode	500	91.79%	79.47%	372	WhiteShadow 478.40
Level 3 ToyPatrol	1200	47.80%	3.23%	601	antimatter 742.48