
Match Editorial 
SRM 78April 9, 2002
Match summary
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+1n 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+1nm or 2k+2nm 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.cuttheknot.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 

By
lbackstrom
TopCoder Member