For the second year in a row, UO Computer Information Sciences, and Information Services are hosting the Pacific Northwest Regional ACM Intercollegiate Programming Contest. On Saturday, 22 teams of three, will enter the lab and use their geek powers in an attempt to solve as many of the given problems as possible in 5 hours. I really hope no one wears a cape this year.
My job in all of this is to act as the systems administrator for our site. This means that I set up the computers to the specification of the overall contest rules. It’s a great gig, really. I get to hang out with geeks all day, which I truly enjoy. I also enjoy knowing that as geeky as I am, I’m still the coolest person there. Seriously, nobody better be wearing a cape or Quidditch outfit.
The problems range from tricky, to downright devious. I only saw one problem last year, the “easy” one. This was a problem that every team solved; and, several teams solved it in a couple of minutes, IIRC. Here it is:
Tetrahedral Stacks of Cannonballs
WALL•E™©, as he cleans up and organizes the depopulated Earth, has come upon some Civil War memorials.
He is consolidating the cannonballs into one location, and decides to use pyramids with triangular bases rather
than ones with square bases.
In Civil War memorials with cannons and stacks of cannonballs, the cannonballs were sometimes stacked as a
four-sided pyramid, with the base as a square of cannonballs with n balls on each side. An alternative is to
stack them in a three-sided pyramid, which is in fact one of the Platonic solids, a tetrahedron.
This tetrahedron of cannonballs has a base that is an equilateral triangle of cannonballs with n balls on each
side. The number of balls in that triangle is given simply by adding together the numbers from 1 to n. On top
of each layer (starting from the base) is a triangle with one less ball on each side, up to the top-most layer with a
single ball.
Given the number of cannonballs on each side of the base, compute the total number of cannonballs in the entire
tetrahedral stack.Input
The first line contains a single number n, giving the number of tetrahedral problems posed, for a maximum of
100 problems. Following that are exactly n lines, each with a single number giving the number of cannonballs
on each side of the base for a tetrahedron of cannonballs, a number greater than 0 and less than 1000.Output
For each problem, output the problem number (starting from 1), a colon and a blank, the number of cannonballs
on each side of the base, one blank, and finally the total number of cannonballs in the tetrahedron.
Sample input Sample output
6 1: 1 1
1 2: 2 4
2 3: 3 10
3 4: 5 35
5 5: 27 3654
27 6: 999 166666500
999
For the quick teams, the gimme of this problem was probably the clues about tetrahedral numbers. It’s a simple math problem. To people who don’t think in any kind of math (no matter how simple some geek tells us it is thankyouverymuch), even a problem like this could be dizzying. That’s where some strategy might come in handy.
To be successful at these problems you’re going to need to have some broad skills come into play. First, you’re going to have to have a strong contingent in the abstract math realm. However, to even get to that you might have to be able to unpack a word problem, so reading comprehension is key. After you get the problem fleshed out in the theoretical sphere, you’ll need a more real approach, codifying abstract algorithms requires a good knowledge of the language at hand, as well as an eye for detail. No matter how geeky you think this is, the accomplishments here are doing these kids a lot of good.
Now, I know most of us aren’t going to equate this contest to a sporting event. It’s kind of hard to root for geeks in the first place, let alone when geeks are engaged in an activity where the only visible action is the receiving of helium balloons, one for each successful completion (each problem has a color associated to it). Still, I’ll be pulling for the old green and yellow. There is a team this year that is composed of two CIS students and one math major. Math for the conceptualization and unpacking of word problems, and two hackers to make it all happen on the boxen. It would be nice if the UO had a team in the top three, and they might be the ones to make that happen…. unless they are wearing f&%#ing capes.
In close I challenge you to do a simplified version of the problem above. Try to find a process for finding the number of balls requested. Don’t worry about programming it at all, just see if you can conceptualize the solution… there is always a geek who can hack it into a program later. 