2015 Challenge24: Finals

The finals for Challenge24 are behind us. Here you’ll find the final scoreboard. So far, the detailed scoreboard/scoredump haven’t been published. I participated in the same team as last year: together with meret and marek.cygan we formed the HoChockiGon team. That’s us:

2015 Challenge24 Winners

We won Challenge24 for the first time, but we managed to win all of the 24-hour contests in a row (Marathon24, Deadline24, and now the Challenge24). In the first two, Mojito1 competed with us instead of meret.

Ok, enough bragging. Let’s focus on the contest itself. But I’ll warn you. I’m not going to focus on everything that went wrong with the contest since this post would be three times longer. Moving date of the finals, lack of communication before the finals, lack of documents describing what’s required during the finals, too few problems for 24h, problems that weren’t tested at all, misleading answers during the contest, scoreboard that wasn’t updated in real-time, descriptions written in “google translate”-like quality, invalid inputs, just to name a few.

It’s worth mentioning that the task-writing team had changed this year. I have no idea why they have to rotate the whole team, but apparently that’s how the things run there. Last year, we had sufficient number of problems even if the competition would last 48 hours. At the same time, after disastrous eliminations (5 out of 6 problems had serious issues and some of them weren’t even resolved), I believe no one had high expectations for the finals. I also hoped, that organizers would learn the lesson and have not prepared half of the tasks the night before the contest.

I guess by now everyone got the big picture, so let’s dive into the problems. I’ll try to explain all of the interesting details of the problems so you don’t have to read the statements. But just in case, here they are. During the contest, I was working (and playing) on Ping-Pong and Carnival Shooter. I also helped a little with PRISC (which was a fantastic problem, except for one slip up) and acted as a team captain/secretary (deciding on the general strategy, doing the IRC stuff and refreshing the standings every other minute).

Classics – Pool, Hypercubes, Matrix

There were three classic problems and all of them were pretty easy tasks.

Matrix was a very weak filler task and let’s just forget it.

Hypercubes was a nice math puzzle. I’ll paste the short description here: “Find the position of n pieces of k dimensional hypercubes in the k dimensional space, where hypercube placed next to each other cannot overlap, but interconnect with their k-1 dimensional sides. What is the maximum number of these joint k-1 dimensional sides?”. The nice thing about such problems is that even if you’re not able to solve them on paper, you can write a suboptimal solution in order to see how it behaves on smaller tests and extrapolate that behavior to produce your final solution.

Last problem was Pool, which is an example of “I’m hell as sure that the tests are very easy, so let’s write a heuristic solution”. A simple hill-climbing solution (initialization: random matching; evaluation: sum of absolute differences over all fishes; transition: swap two random pools) solved the tests in no time. In our case, we used ILP at first, but it solved only 6 tests after 1 hour of running.

Ping-Pong

This was an interesting task, very reminiscent of the task Ball from last year. We had the following hardware prepared onsite:

The only thing you controlled was the position of the arm (angle only) and the power of the fan. Those parameters were sent over TCP/IP to the server. The goal was to put the ping-pong ball inside the hole within two minutes. Additional obstacles were gradually added to the playground, which made the task more interesting.

The task came down to writing a proper manual interface and learning how the ball behaves in various positions of the fan. My interface looked like this:

ch24-b

When I clicked on it, my program sent message to the machine. I used the position of the click to calculate the angle and the power (based on distance from the center). Left click updated angle only, middle updated power and right both of them.

My biggest mistake was that I didn’t do enough test runs during the first 6 hours (which were a testing period). While everything worked as intended, I had no clue how the ball behaved when blown from different angles. During the first part (no obstacles) I managed to complete it only once out of four times. After that, I spent around 90 minutes staring at the machine to get the idea of how exactly it works. Thanks to that, I was able to complete all of the remaining 7 rounds (one was canceled) within given time.

Overall, I really liked the problem. I believe that this time the challenge was more fair, than the last time. Mostly due to the fixed schedule, thus each team had the same number of tries. The only problem was that because the order of the teams was fixed, the first team was always at disadvantage when the new changes were introduced.

PRISC

Challenge24 is particularly known for having tasks that deal with new programming languages. This year, they used a simplified assembler and provided us three different programs written in that language, without telling what each one of them does. Our task was to optimize it (both speed and size), which effectively turned this problem into an optimization challenge.

The thing is, the choice of operands was well-thought. The same goes with the scoring, which added a lot of depth to the problem (without adding too much unnecessary complexity). The choice of three programs was also great. Each of them was quite different and required different approach. All in all, PRISC was pretty much three different well-prepared tasks and single-handedly made the whole contest a worthwhile experience.

The first program had to print 99 bottles of beer “song”. The second was a simple sorting of an array and the last one had to visualize some region of the Mandelbrot fractal. Meret converted those programs to c++ versions and he also added name aliasing for the provided PRISC compiler.

In the case of last program, it was clear that compressing the potential output might be much better approach than solving the actual problem on the fly. We wanted to have a rough estimate on the used parameters of the tests. We began submitting “probing” solutions that gave us one bit of information each about the testing set. Essentially we just added an assert which generated an invalid output in case it was false. It took us dozens of submits, but after nearly 10 hours of submitting we knew that there’s only one test case, and in case of C3, we actually knew the exact input. It’s “-20 -200 20 -130” if anyone wonders ;) Just in case, instead of simply outputting the required string, we wrote a program that compresses it.

Our solution to C2 used much less exploiting. It used the fact that the integers were uniformly distributed over a very wide range (if I remember correctly, they were all between 230..231). It was a mix of bucket sort and insertion sort. Each number was initially put into its bucket. If the bucket was already occupied then the potential swap could happen and the pointer moved into the next bucket. This loop repeated until an empty bucket was found. In the end, we were left with situation where we had several sets of sorted integers and we just had to print them out, while skipping the empty buckets. This works O(n2) worse time, but it’s expected O(n) with a small constant when integers are uniformly distributed.

Links to our final submissions: C1, C2, C3, and finally the program that generated solution to C3. We had around 350 points for C1 and 400 for both C2 & C3. In case of C2, I believe we had around 20% better score than the next person.

To be honest, I didn’t mind that there was only one test case for each of the subproblems. We would still use test case probing, and I’m pretty sure that we would still get a sick advantage on C3. At the same time, I was later told that the organizers explicitly stated on IRC that there were multiple test cases, which obviously wasn’t true. Another major problem was that apparently they also told that the final scoring was linear which also wasn’t true. As far as I can tell, the scaling function that was used was similar to what have been used in the past: “SCORE := round(400 * (1 – sqrt(1 – S/Smax)))”, where S is your team’s score before the scaling, and Smax is the best score among the all teams.

Carnival Shootout

This is the task that should win the award for having most confusing problem description. Even input and output are switched. The task itself is a multiplayer game somewhat similar to Tic Tac Toe. It’s played on a large square grid and in each turn you can color one of the cells. The turns are simultaneous and each player uses his own color only. The goal is to have the longest line of cells after some fixed amount of turns. Some additions: if the cell was already colored, then your move was clearing it; if many players wanted to perform the same move then there was no effect; grid was essentially infinite since it automatically enlarged when someone made a move on the border.

Not only the server didn’t work during the first 7-9 hours, but the game was horribly designed. In essence, the optimal strategy was to just build a single segment away from the center and hope that you won’t cross with anyone else. There was some additional meta-game involving last few moves. You were guaranteed to split any line in two with your last move, which was better than adding one more point to your own line. Except for screwing the first few moves, there was no real place for improvement.

Around three hours before the end, they drastically changed the rules of the game. There were two important changes: the game no longer automatically increased the size of the board and there were some additional pool of points for removing enemy cells. I really liked the new problem since it finally posed some challenge. Unfortunately, they didn’t gave us enough time to modify our solutions (around 30-45 minutes), considering they also modified the input format.

My AI for this game was very simple. It tried to extend the current longest line using distance from the center as a tie-breaker. There were few small additions, but that was the basis for it. My biggest advantage over others was that I could play manually. Since the server allowed us to send our moves several times, my AI automatically generated the “default” move and then I could manually override it (by clicking on a cell). My interface was very simple and looked like this:

ch24-f

My cells were colored green, and the other players used red. I probably could have made it better and differentiated between the most important opponents. Unfortunately, I didn’t have time for this, because I had to spent last 3 hours playing the game non-stop :) In order to go to the bathroom I had to teach meret the basic strategy and let him play for a few minutes :) I believe we got the best scores in the last two rounds, but without knowing the detailed results I can only guess.

Conclusions

Probably the saddest moment throughout the whole contest was right at the beginning when we saw that there are only six problems. One of the biggest thrills in Challenge24 came from being overwhelmed by the amount of work that has to be done in the next 24 hours. This year, we were able to polish our solutions to every task there was. Which isn’t bad itself. It’s just that it’s not what the last two years of Challenge24 prepared me for.

Anyway, I must say I still had fun during the contest. The first few hours where nothing worked, were really irritating. But then, we started working on PRISC problem, Ping-Pong got more interesting course and in the last hours Carnival Shootout finally became a fun problem to work on. I also used the event for testing out the prototype of my game, so that’s another thing going on for me.

And that’s all. Thanks for reading.

2 thoughts on “2015 Challenge24: Finals

Leave a Reply

Your email address will not be published.