With the TCCC finals around the corner, now is a good time to look back at the three exciting online rounds, as well as look forward to the Championship round on October 31.

Online Round 1 - Scruffle

Scruffle is a game inspired by the ubiquitous board game Scrabble. Contestants are given the values of all cells and a dictionary of allowed words. Each cell has a word or letter multiplier associated with it, influencing the score for placing a letter or word at a particular location. The goal of the game is to place words from the dictionary onto the board (in any order) and maximize the score.

With 363 competitors competing for 300 spots in Round 2 (and a TCCC Marathon t-shirt), getting just 40% of the top score was good enough to pass. Most passing contestants (including the top scorers) used variants of the same strategy, considering placing all words in all possible locations and then greedily selecting the best placements.

In the end, blackmath topped the rank list, with AdrianKuegel coming in second.

Online Round 2 - DeepMining

 

Based on the online Flash game MotherLoad, DeepMining placed contestants in charge of a mining operation. A machine is available and it can drill through the terrain and collect minerals: the deeper the terrain, the more valuable the minerals. The machine has a fuel tank with limited capacity that cannot be refueled. It also has limited cargo bay capacity, but can return to the surface and off-load collected minerals. The goal is to return minerals worth as much as possible to the surface before running out of fuel.

The tricky part is that the terrain (and with it the locations of minerals) is not initially revealed - as the machine moves, it reveals a small block of terrain around it. Another caveat is that, although the algorithm for generating the terrain is given, some of its parameters are hidden, so good solutions have elements of statistics and probability in them to estimate those parameters.

Successful contestants recognized two main strategies: going deep or staying near the surface. Going deep worked well because it allowed for collecting more valuable minerals, but at the same time, it was more fuel-efficient to stay near the surface and collect the low-value minerals. There were different ideas for choosing between the two strategies.

Catching one of the 100 seats in Round 3 was much tougher than in Round 2 and a score of almost 86% of the top score was needed. doudouille won the round, with Krzysan in close second. Both had additional ideas that separated them from the rest of the pack.

Online Round 3 - Advertising

Round 3 saw 100 contestants battling it out over two weeks for only 8 finalist spots.

 

The problem presents a model in which our company has produced a product and is trying to attract customers. Undecided customers initially prefer the competitor's product over ours, but we can place advertisements to offset their advantage.

Undecided customers can decide on one of the two products in two ways:

• Direct advertising: when we place an ad, users will be influenced by it (how much depends on their distance from the ad). We can also place many ads at the same time, which will have a greater effect. Our competitor never advertises its product, which gives us the edge we need.
• Word of mouth: customers who have purchased either our or the competitor's product will tell nearby undecided customers about the one they purchased, increasing the likelihood that the undecided customers will also buy that product.

The goal is to maximize our profit by attracting many customers, while spending as little money as possible on advertising.

An aspect of this problem I found interesting is clustering the customers. It is very easily done visually - if you look at the images on the right, you will easily see seven large clusters of points. However, developing an algorithm to do this for you is far from trivial.

The effects of direct and viral advertising were described in the problem statement with formulas. Some of the parameters were unknown, but could be estimated with an initial probing advertising run. As usual, trying many different approaches was crucial for getting a good score.

The final results were somewhat of an upset, with three competitors dropping out of the top 8. PaulJefferys took the win, ahead of Maris and doudouille.

The Championship Round

The top eight performers in Online Round 3 have been selected as finalists and will take each other on at the 2007 TCCC onsite finals. Three of them (doudouille, Mojito1, and Maris) were finalists in the 2007 TopCoder Open Marathon track earlier this year, with Mojito1 winning the competition. At the time of writing, doudouille is the top rated Marathon competitor, clinching six top-five finishes in the nine TopCoder Marathon Matches he participated in, and is definitely a strong contender for the overall win.

All competitors will have to adapt to a restricted work environment and a 9-hour round, quite a contrast to the one- and two-week online rounds.