2007 ACM Collegiate Programming Contest Problems

[dstefan]

See attached - they look very interesting

 

[Stefan Zota]

This is the top college level programming contest. In some way it is a continuation of Informatics International Olympiads. The main difference is that it is a team event rather than individual.
The background required is not more than high-school olympiad: very strong graph theory and dynamic programming.

As far as I know, the level is slightly higher than International Olympiad for 2 reasons:
1. extensive training is done in each university, the results are important for them
2. priority for most strong C.S. programs in U.S. and Western Europe. High-school olympiad does not have the same focus in the States.

 

[doug reich]

The competition does not seem that hard; just unpleasant. A number are well-known problems covered in an algorithms class (I should know; I took one), and are mainly about the programming of those algorithms.

 

[Stefan Zota]

I would have to disagree here.
If the text of a problem is accessible to a large number of people that does not make it easy. Informatics contests are well-known to have this approach as opposed to Math or other sciences with more cryptic problems.

Competition encompasses different research areas from graph theory to real-time scheduling. It does not include numerical methods, linear algebra, statistics, directions relevant to a quant. Informatics is one of the few sciences that has such a broadly recognized event at college level. You can find a lot of information online.
The ACM-ICPC International Collegiate Programming Contest Web Site sponsored by IBM

 

[doug reich]

I would have to disagree here.
If the text of a problem is accessible to a large number of people that does not make it easy. Informatics contests are well-known to have this approach as opposed to Math or other sciences with more cryptic problems.

I agree it is definitely a different type of exam than, say, the Putnam (Putnam Directory). However, if the solution to a problem (e.g. bin packing or graphics rendering) is taught to all CS majors who comprise the competition, where is the challenge? Is it a programming or a computer science competition? Do they read your code and grade you on quality? Or does the ugliest but quickest written code win?

 

[JeffSmith]

Sure, they teach these in college, but being exposed to an algorithm is completely different than being able to quickly apply them to a problem in a competition. Some of the questions can also be approached from many different angles with faster approaches.

These competitions test they synthesis of this knowledge. Can you select the right algorithm to solve a problem? Can you quickly code up this solution?

To me its very similar in spirit to other competitions in math in physics.

 

[Stefan Zota]

I agree it is definitely a different type of exam than, say, the Putnam (Putnam Directory).

I don't know details about Putnam competition so I cannot comment here.

However, if the solution to a problem (e.g. bin packing or graphics rendering) is taught to all CS majors who comprise the competition, where is the challenge

I feel we are going in circles. Which problem are you pointing to?
There is no algorithm taught in school that will be sufficient to solve ACM problems. In the best case, you may find a similarity with a problem from past olympiads and extrapolate a solution.
This is international olympiad level. Dan can say more about Math International Olympiad problems to make a parallel.

Is it a programming or a computer science competition?

Neither of them. Algorithms is the only focus at all Informatics olympiads (high-school and ACM).
Programming can be done in any language. When I was in college, most people were using C or Pascal. No need for OOP.

Do they read your code and grade you on quality? Or does the ugliest but quickest written code win?

It does not matter the code beauty, does not matter the speed.
All that is important is to get the right results at all tests and of course to finish coding in allocated time.
Some informatics contests do involve a quick code review. The goal is to validate the algorithm from a general perspective. For instance, if I am unable to solve a problem, my goal is to get 10% of results right. I code a Monte Carlo style algorithm if the range of results is small and I may be lucky a couple of times. The results would be canceled if found in the review.

 

[doug reich]

Since you have a stronger background in this than I do, I'm going to assume I didn't think through the problems enough. (bin packing, I was thinking of the container ship problem; graphics, there were few, I was specifically thinking of ray tracing re: the roofing problem; the blood type one seemed very straightforward)

 

[Stefan Zota]

bin packing, I was thinking of the container ship problem;

Bin-packing is NP-hard which means a brute force approach cannot be used to solve the problem.
However this problem is a particular case since the requirement is not to find the actual combination of containers but rather the number of required stacks.
My first guess would be to try a dynamic programming approach to determine a certain recurrence.

graphics, there were few, I was specifically thinking of ray tracing re: the roofing problem;

Ray tracing is a very nice algorithm in graphics though I do not believe it applies here. The complexity of the algorithm is given by number of pixels * number of objects.
Number of pixels is not limited here, it is purely geometrical problem. Also the view source is not clearly defined, needed in ray tracing.
The goal here seems to be to purge gradually from a list of triangles until all the ones left are visible. So we would need to define visibility mathematically then hopefully get some analytical geometry conditions for 2 triangles to overlap in user view.

the blood type one seemed very straightforward

First reading and sample tests confirm your statement. I am surprised, I am probably missing something. Initially I thought they would ask to recompose an entire tree ...