Overview

Parts updated since being first put up are in emphasis like this. For searchability, they will also start with “UPD:”

This is the specification for the Bonus assignment. It is worth 4 bonus marks. The intention is to give you some experience with outside contests and to be something fun if you either enjoy or are maybe interested in competitions.

For the bonus assignment, you will form teams of 3 and attempt a past ICPC style contest.

Background on the ICPC

The ICPC (International Collegiate Programming Contest) is the main programming competition for university students. The overall competition is structured as a league. The first qualifying rounds for each region tend to start around September of each year. Depending on region, there may be one or more qualifying rounds, eventually culminating in the ICPC World Finals. Traditionally, UNSW has often sent a team to the ICPC World Finals.

Contests within the ICPC generally all follow a similar structure:

  1. They are 5 hours long.
  2. They are done in groups of 3. However, you are only given 1 computer.
  3. There are around 11 problems. Problems can cover just about any topic. Problems are also in any difficulty order. The submission system is similar to (or identical) to the one you used in Contest 1.
  4. Either you can use unlimited printed material or there is a limit of 25 pages.

The 3 groups, 1 computer structure and large number of problems leads to some interesting dynamics:

  • It is important to be able to roughly judge what are the easies and what are the hard problems.
  • Time on the computer is an extremely valuable resource. To not waste it, it is important to be able to plan an algorithm and a rough implementation on paper.
  • Leveraging your teammates is useful. Naturally, each of you will have their own strengths and your team will be a lot stronger if you can harness these strengths effectively.

The team aspect also makes it a lot more fun for me. I like having someone else to bounce ideas off or to sanity check my algorithms/code.

Assignment Details

If you are planning to attempt this assignment, form a team of 3 and let me know in advance what your team is. If you have a contest in mind, let me also know what contest you are thinking of. Otherwise, I can provide a suggestion.

UPD: 3 is preferred. If you must, you can do 2 or 4 though.

This assignment is meant to be fun so I’m not going to be strict. You do not have to do the contest under full exam conditions. So

  • Feel free to use online resources (though don’t just google for the solution…)
  • It is up to your team whether they wish to use just 1 computer. If you decide to individually each use a computer, I would recommend to still physically do the contest together. It is a lot easier to explain an algorithm in person than over the internet.
  • You don’t have to try the contest for the full 5 hours. However, I would recommend you at least try until the point where you think you can’t make any more progress.

After attempting the contest, as a team do a writeup of your experience. Roughly, for each problem write how your team went about solving it, what the crucial ideas or observations were and a summary of the solution. Depending on difficulty, this could range from a sentence to a page but please not much more than that. Really, the shorter the better.

Then, as a team, pick 3 problems you find interesting but did not solve and attempt to solve them. Then, possibly with the help of hints or the editorial, write up a solution summary, similar to the above, for these as well.

Send me the writeups. Also send me proof you attempted the contest (depending on platform, preferrably this is a link to your account or the scoreboard).

Marking

This assignment will mostly be marked on effort so I expect you to have a genuine go but don’t stress the writeup too much. However, I do expect something legible, if you have doubts, feel free to send me a sample first for feedback.

Due at 23:59:59 on Sunday the 15th of December (the first Sunday after the end of the Exam Period).