JOIN
 Match Editorial
 Room 1 Review Archive Rookie Review Discuss this match Problem Set Want to write a feature?
SRM 78
April 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+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 1PoemCode 250 99.07% 96.28% 221 NDBronson244.20 Level 2Pinball 450 95.81% 51.63% 326 Logan412.42 Level 3CleaupCrew 1050 30.23% 11.16% 631 thekcc981.45 Division II Level 1Scoreboard 250 97.65% 97.07% 240 kokon249.16 Level 2PoemCode 500 91.79% 79.47% 372 WhiteShadow478.40 Level 3ToyPatrol 1200 47.80% 3.23% 601 antimatter742.48

By lbackstrom
TopCoder Member