Get Time
statistics_w  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

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

Submission Rate Submission Succ. Avg. Pts.
High Score
Division I
Level 1
250 99.07% 96.28% 221 NDBronson
Level 2
450 95.81% 51.63% 326 Logan
Level 3
1050 30.23% 11.16% 631 thekcc
Division II
Level 1
250 97.65% 97.07% 240 kokon
Level 2
500 91.79% 79.47% 372 WhiteShadow
Level 3
1200 47.80% 3.23% 601 antimatter

By lbackstrom
TopCoder Member