Blog

Tips for contestants

tips_contestant by Tibor 'Igor2' Palinkas on 2020-03-08	Tags: behind, howto, prepare, tips
node source

Abstract: In this article I share my non-programming tips for increasing your scores on challenge24-like competitions. Doing these things right can easily move your team up on the scoreboard by better allocating your resources on things that really bring scores to your team.

It is important to note that most of these tips assume a rule-book similar to Challenge24's.

Resource management

Read all tasks before coding anything!

Top finalist teams usually featured 3 universal members, each could solve any of the problems equally well. Less fortunate teams had more of specialized members: some better in algorithm theory, some better in coding and debugging. Some knowing a lot about math, others knowing a lot about network programming. Assigning task per skill makes a huge difference; the difference between getting score and wasting many hours on things that would have been 15 minutes for your team mate.

Look at the scoring for tasks. The "optimization" or "game" type tasks, the ones where your output competes with other teams are usually not really good to start with, because you can spend any amount of time on optimizing the solution a bit more, trying to beat the next best team while you don't get bonus for having a solution early on. So it's usually better to finish static I/O tasks first then use the remaining time on optimization tasks.

On the finals, there was usually a hardware task. A hardware task has a physical bottleneck: if all 30 teams have a submission pending, the queue that is waiting for the actual hardware is long. So even tho it's usually not the static I/O kind of task, it may be a smart move to start on the hardware task early on, at least do the research/testing/experimenting phase and come up with an initial working solution, to secure score - then the optimization part can be left to the end. With such strategy, with a minimal working solution you already can score a lot, more than those half of the teams who typically start too late and don't get a real chance to finish any working solution before the round ends!

Team work

Challenge24 was a competition for teams. A bunch of guys working independently is not a team. If you get stuck with something, ask your team mates, they may know a quick solution!

Some big tasks may require multiple skills: network programming plus algorithms or signal processing plus low level (virtual machine for an exotic programming language). If you work as a team instead of trying to solve the whole task alone you may code these faster than other teams and earn the time bonus.

Coding time vs. runtime vs. all 10 input files

A good task has input files that are getting gradually more complex and hard to solve. Most of the times these tasks are scored with submission time in mind: the earlier you submit the right result, the more score you get.

Especially on a short event like an EC, it may be worth considering this: you may go for a smaller, simpler, even plain brute force solver that can solve only the first 4, relatively small/simple input of 3 tasks very fast. That means you scored for 12 submissions with the bonus of early-submission time for about half of them, compared to spending the same amount of time developing and debugging the proper solution for one task. In other words: you spend less time on coding but the resulting code is slow and will spend more time running, which limits you on how many files you can solve. But at the end of the day submitted output files matter, not how elegant your code was.

Bonus: once you finish submitting the first few files, if you prepared well and have enough spare CPU power and memory, you can leave your dumb solver there for the rest of the round. If you are lucky, it may be able to solve one or two more input files before the deadline.

This works best if you do this for tasks that you think you won't be able to solve perfectly (high risk tasks) because you are not sure you know the right algorithm or that you can code it without errors.

Optimization/game: don't be the best

In optimization/game tasks there will always be a few teams spending a lot more resources than others, having much better results. However, this may take too much of their time, not scoring a lot in other tasks. At the end, it doesn't matter if you were 1st or 2nd in one specific task - what matters is the sum of scores on all tasks!

The game/optimization tasks may also be a bit additive, plus there is an effect of "I've invested so much time in it, if I only invest 10 more minutes I could bet the next team..." Try to resist. It's usually enough if your score ends up in the first 1/4 or 1/3 of the scoreboard for the given task - especially that there will be teams not even attempting to solve it.

The good time to spend extra effort on these tasks is around the end of the round, when you have finished with everything else you could reasonably solve. Then it is fair to use the remaining time to do small optimizations, improving your score a bit in these tasks.

Realize if it won't work

A perfect team normally wouldn't spend any time on tasks that they won't solve. This is because they look at the task list and decide which one they can solve for sure. But in real life most teams are not perfect and most decisions are not perfect either. It happens that a task looks doable and you start working on it but after spending some time you face problems that you and team mates can't solve. This may be the moment to switch to another task.

The decision is hard. Sometimes simply the fact that you have already invested a lot of time in a task makes giving it up such a waste. This is a good choice if you then finish the task and earn scores, but can be a bad choice if you invest a lot more time and then have to give up.

There is no good recipe to avoid the latter. There are some considerations tho:

before you start, estimate how much time a task will take, and if it already took longer and you don't yet see the end...
... consider postponing this task and switch to something that gets more score sooner
... ask your team mates, there may be something you missed and they can point out

Scope: solve only the 10 input files!

There are tasks coming with input files and a known good solution. In these tasks your solutions are not directly competing with other teams solutions. These tasks usually have a single good solution for each input and there's no room for optimization - you either produce the right output or not.

It is very important to notice that you do not need to have a perfect, generic solver, but something that only solves the 10 specific input files provided. Sometimes (especially if the task writers wanted that and did a good job) the simplest solution is the generic one. But in many cases there are simpler, cheaper approaches that happen to solve the 10 input files you get your score for while may fail on arbitrary other input files - which are irrelevant in scoring.

Visualize: look at the input files

Before you start solving a problem, even an algorithmic problem, do visualize all inputs available. You may notice a pattern. The input files may have some common, special property that can simplify your life by allowing you to write a less generic solver.

Corner cases

Whenever you bump into some tricky corner case while writing the solver, just check if any of the input files (you want to solve) have it. If not, just don't handle it, because the code you write for it will not get executed in any run that is done for score.

Preparation

Be fit

Especially if you are first time finalist, it may be worth practicing this with your team: staying up for more than 24 hours and being productive for most of the time is not automatically easy for everyone. But with one or more practice sessions beforehand you can figure how this works best for you (e.g. coffee/energy-drink/cola/sugar intake, whether 20 minute nap helps or kills your remaining productivity, etc).

Try solving previous problem sets

... for real. It is different to read and understand a task and actually solving it. Even better if you try to solve tasks as if you were on the competition, aiming for shortest time instead of exploring the problem.

Practice team work

Even better if you do this together with your team: that may help figuring how to do your team work best.

Prior knowledge

There are a few things that your team absolutely need to learn before the event. And by learn I mean having some experience programming these things. If you are trying to pick the knowledge or experience up during the event, you will lose a lot of score. These topics are:

algorithm theory (obviously)
a few different programming languages; how to write throw-away code real fast in them
how to process huge amount of data (including how to allocate gigabytes of ram)
minimal input parsing - look at how a typical task input looks like
loading image files (png, bmp, custom formats)
loading sound files (typically wav with a very specific header)
network programming (connecting to a TCP server, receiving UDP packets, including broadcast packets, sending UDP packets)

Libs

You can use libraries and code you prepared before the event. Look at the above list and look at previous years' tasks. You will find some recurring themes, e.g. being able to load png files. If you have ready to use code for that in your favorite programming languages, you save a lot of time!

For many things you don't need to have a lib with proper API - it may be enough to have a well commented example code that can be copied and modified.

Existing software

Sometimes parts of a task can be solved with existing software:

preprocess some input, spitting out partial solutions (e.g. qhull)
ready to use solvers: your task may be reduced to translating the problem input file into the format the solver needs (e.g. lp_solve for linear programming or prolog for backtracking)
unexpected connections in some free-form tasks

An example of the unexpected connection is one of the tasks in the 2006 finals: we had to transfer data over a headphone-microphone link. There are a lot of different protocols readily available for this: there are software low baud rate acoustic modems, DTMF encoders/decoders, etc. We, as contestants, always took a full Debian repository with us. I solved that problem with DTMF because I found easy to use tools for DTMF in our local Debian repo.