Friday, April 4, 2003

Problem Set Analysis & Opinion

Semifinal Round 1 proved to be one of the most exciting in recent history. Yarin and Evd raced to see who would complete the easy first, while StefanPochmann worked diligently on the hard problem. Yarin was the first to finish the easy, and immediately started the medium, with Evd close behind. Yike submitted the easy soon after. StefanPochmann began testing his hard early shocking onlookers, but wasn't ready to submit till much later. After Yarin submitted the medium, StefanPochmann submitted his hard. Things were beginning to get crazy, when onlookers saw Stefan wasn't opening any of the other problems. Then, Stefan recompiled the hard alerting spectators to the situation at hand. Stefan later resubmitted the hard, and soon after, submitted the easy. Yarin raced to try and complete the hard, but couldn't finish on time. Only one challenge was issued during the challenge phase, an unsuccessful attempt by StefanPochmann. Once systests were done, Yarin clearly won, with Stefan failing on both of his submissions. In the end, nobody correctly submitted the hard. Once the round was over everyone was in agreement, the set was "evil", particularly under tournament conditions. SnapDragon said afterward, "If I'd competed in it, I'd have gotten 1 question!" Good luck to Yarin in the next round.

Value	200
Submission Rate	4 / 4 (100.00%)
Success Rate	3 / 4 (75.00%)
High Score	Yarin for 170.84 points

In this problem, coders are given the initial number of students in each college major, as well as, the tendency for students to switch majors each year. To find the final number of students in each major, you can iteratively apply the yearly major switches for the required number of years. The trick here is to carefully round all results, so there are no fractional transfers. That way, the number of students at TCU isn't changed as a result of imprecise arithmetic.

Value	550
Submission Rate	1 / 4 (25.00%)
Success Rate	1 / 1 (100.00%)
High Score	Yarin for 337.35 points

An easy way to solve this problem, given the restrictive input constraints, is to create a large two dimensional array. By using a fill algorithm, all of the regions of the plane can be labeled thus giving the total number of regions. A more inspired solution, that would work on much larger inputs, would make use of Euler's formula:

n - m + f = 1 + k
where n represents the total number of line endpoints or distinct intersection points
m represents the total number of line segments
f represents the total number of regions
k represents the total number of components

Value	1000
Submission Rate	1 / 4 (25.00%)
Success Rate	0 / 1 (0.00%)
High Score

This problem is all about building parse trees. The first is built while trying to validate the correctness of the expression given. A simple recursive descent parser can quickly check whether the input adheres to the required grammar. If the grammar is valid, the parser can be coded to produce a tree representing the input. The interior nodes of the tree will be operators while the leaves will be numbers. Once the main tree is built, the minimum implementation cost must be determined. This can be calculated by traversing the tree in a bottom up fashion. At each node, you can determine which subtrees rooted at that node exist in the available instructions. This requires that the instructions be parsed as well, and built into parse trees. The subtree producing the minimum cost becomes the value for that node. The cost of a subtree is the cost of its leaves, plus the cost of the instruction required to process the subtree. Once this process is complete, the root of the whole tree has the best possible cost.