Match Editorial

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

The Division-II Easy problem wasn't hard, though perhaps somewhat easier in Java. You simply had to count the words (with StringTokenizer), then modulus with the number of items. Note that if you got 0, you had to return the number of items, *not* 0. C++ made it a little more difficult due to no really easy way to count the number of words - however, you could count the number of spaces instead and add one, since you were guaranteed only one space distance between words and no leading/trailing spaces.

The Division-II Medium problem was mostly simple. You simply had to add up the scores for each player. There was some vagueness on the precise scores for each place, and it took a little math to come up with an array of { 6, 3, 2 } for this (many people hardcoded it). After that was done, one could simply add up the totals, then choose the lowest score, put all the people with those names together, and sort, and you're done. The only tricky bit was figuring out a way to hold all the players, but as they limited it to 100 player names total, you could use a static array, a map< string, string >, or a HashMap.

The Division-I Easy/Division-II Hard problem started off the Div-I problem set with a rather easy brute-force problem, the type of which many of us have seen before. Whenever you see an item set that goes from 1 to 20 elements, this algorithm is a good bet. Basically, you try every combination, and keep track of the best answer. That's it. ZorbaTHut (me) did it recursively, while John Dethridge counted from 0 to 2^20 and turned each number into a possible solution using its binary representation. Basically all the solutions fell into one category or another.

The Division-I Medium problem was also a brute-force deal. Take the "target" and find all his parents. Then find all *their* parents. Then find all their children. Then remove the target and the result of step 1 from that. And there's your result (after you sort it). C++'s set<> came in very handy, since it not only sorts automatically but insures uniqueness (no point in storing a parent twice, and uniqueness is bad on the final step.) It's not the most elegant solution in the world, but it will easily run fast enough. ZorbaTHut built functions for "find all children" and "find all parents", so it may be easier to read. malpt has an equivalent solution using Java's HashSet.

Somewhat annoyingly, the Division-I Hard problem was solvable brute-force as well. My solution generated all the possibilities recursively, and for each possibility, it made sure every single result in the list was consistent with it. I had to write a little generator to compare two possibilities, then it was just a matter of comparing how many potential solutions were found. If it was 0 solutions, it was invalid. More than 1 meant unknown. And 1 gave us the answer (which presumably we've stored somewhere.)