2014 Challenge24: EC

Intro

In the past I heard a lot of skeptical information about Challenge24 contest – while the tasks were usually interesting, a lot of them were broken. And this was the main reason why I was always reluctant for giving it a try. Last year I finally decided to compete in it, and that 24-hour final turned out to be the most fun contest, I ever participated in. In terms of variety of tasks, it beats everything else (yes, even IPSC). It features “classical” binary algorithmic tasks, optimization tasks (with relative scoring), problems involving images and sound, and during the on-site we also get our hands on multi-player games and mechanical tasks.

Our team, HoChockiGon, consists of two algorithmic veterans (meret and marek.cygan) and a random university-dropout (myself) ;) This makes it quite easy to split the tasks between us, since they solve all of those unsolvable algorithmic problems, and I get to work on everything else. We’ve lost a lot of time on communication, since each one of us was in a different place, but overall we performed a bit better than expected :)

The Contest

The contest lasts 6 hours. Here you can find the tasks/inputs and all of the relevant information. We don’t have any complex strategy – my teammates just solve the classical problems in order from easiest to hardest, while I’m looking through unusual problems estimating their difficulty.

In the end, I haven’t done too much. First I worked on F – I extracted the dominant frequency at various time steps and googled around the doppler effect. Then I did naive solutions for H and J. Then I begged my teammates to help me with F, since I’m horrible at math/physics, but they didn’t care for my feelings ;) I ran through C problem and I saw that it’s actually quite simple – it just looks complex due to the number of pages. But since Marek finished all of his “classical” problems, we decided that since Marek doesn’t want to do F, it’s best for us that he will solve C. Meanwhile I improved a bit my H and J, and I had a rough estimate of how much time it’s going to take me, to get a perfect/near-perfect scores on them. But with 1,5h to go, I decided to go for F. Strategy-wise it was a poor decision, since we were in the lead, so gathering small but certain points should be the way to go. But at the same time, F looked like an interesting challenge and the results in qualification round doesn’t matter. Nonetheless I failed miserably and we actually had lower score at the end of the contest than during the leaderboard freeze (1 hour to go).

Problem-wise, we had solved A (without last test), B, C (again without one test), E, G, I, some partial points on H & J, and few failed tries on F.

F – Forensics

It was a very interesting problem. First of all, you have to extract the dominant frequency. I had a ready implementation of FFT so I used it, since it literally takes less than 5 minutes to use that. The downside is that it’s going to have errors, but with such huge tolerance (1 meter) I figured out that it won’t matter too much.

Now the fun part begins. I have a time-series of frequencies and I have no idea what to do next. My advanced math/physics knowledge is next to non-existent. Mainly because, you never really need it in the contests – you can always solve everything using iterative methods. I figured out that there are four variables: distance, humming frequency, angle and speed. You can also change (distance, angle) to (x, y) and assume it only moves horizontally. Frequency is somewhat redundant since it’s just a constant that multiplies everything – I used ternary search to compute optimal frequency for given (x, y, speed) triple. Having those variables set, I can simulate the whole process (using a very simple formula from wikipedia) and just compute the RMSE between observed frequencies (obtained by FFT) and simulated ones. My goal is to find the set of parameters that minimize that error.

It’s quite intuitive that there should one global minimum, otherwise we couldn’t find the distance and there would be no such problem to solve during the contest :) And if the variables make any sense, there should be no local minima. So first I generate few (10K) random states, and then I just use a hill-climbing on the set of parameters. If you have a bit of experience implementing it, it takes 5-10 minutes to do it.

With around 40 minutes to end, I had everything ready, but for some strange reason my result on example test was always smaller than the correct one, and I had absolutely no idea why. The optimization heuristic was very stable. Tweaking the quality of FFT did create some changes, but it was still very far from the correct result. I was certain that my function that simulates whole process contains an error, but even though I looked at it 20 times already I couldn’t understand what’s wrong with it. With 10-15 minutes to go we decided to submit F1 by using my result and scale it appropriately. After getting wrong answer I also sent two more submits with +/- 2 changes. In total, my submissions covered result from 801-807 range, while correct one was 800 :)

After the contest (and an additional hour of cursing) I learned from the organizers, that I forgot to include the delay of the sound (i.e. the moment when you hear the sound is not the moment when the sound was created) into my simulation routine. Somehow I didn’t notice that subtle hint about the length of the wave files. Anyway, that was a really tough problem. I’m happy that I was actually pretty close in solving it (although at the same time very far). And the reason why it almost worked for F1 is because example and F1 have the same speed.

H – Tile Design

This is a fun and interesting problem. At first I thought it’s easy – if I’m able to figure out how to generate a random “loop” that covers whole grid, I’m able to solve the task pretty efficiently. Generating random connected pipes will probably give you several loops. But I noticed that 2 loops can be “connected” if they share 2 edges that are right next to each other. But this looked like something troublesome to implement so I tried to search for an easier way. I wanted to have any kind of solution that doesn’t score 0.

It turns out that joining 2×2 blocks is easiest to implement. In this way, when loops are next to each other, they always share at least 2 edges. At first, I randomly connect all of the blocks. And then using the block structure I generate the path. I have submitted my randomly generated solutions without having a function that scores solution. This way I got faster feedback, that my solution actually works.

My later improvements just increased the speed of generating random solutions and scoring them (it can be done in O(N*M) time, where N and M are grid dimensions. This still didn’t gave the perfect scores (60-90 points after few minutes of running for each of the tests), but improving it was actually pretty simple – I could simply test it while generating the loop and revert last few blocks if the “LRPL” gets too big (but as I said earlier, I wasn’t able to do it in time).

J – Image Compression

This is actually a very simple task (simple, not easy). It seems rather natural, that small changes in solution produce very stable result, which means that we can freely use HC/SA here. The problem is that calculating the score takes a lot of time. The first remedy is to start with a decent solution – the easiest way is to create a “grid-like” solution where intensity of each pixel is equal to an average of pixels that can be found in it’s close proximity. The other is to use simplified scoring function, for example you can assume that the weight of each reference point is zero after D pixels. And you don’t have to recalculate weights from reference points that were not changed. So O(W*H*(W+H)) complexity can be reduced to O(D*D) for each step, allowing for few thousands of steps per second, which should enough to get a decent solution.

During the contest I wasn’t able to optimize my algorithm, and each step took O(D*D*(W+H)) time.

Outro

I believe this year’s EC was a bit better than the last one. Like last year, we had very interesting tasks, but this time the problemset was much more balanced, which is clearly visible in the leaderboard (higher spread of scores). And I definitely prefer the 6-hour format with such tasks.

Overall it was a very fun contest and I can’t wait for the finals in May.

6 thoughts on “2014 Challenge24: EC

  1. Márton Ady

    Thanks for sharing your story. It’s funny to read how you and I approached problem F in the same way, and how both of us cursed when our “perfect” solution for the example didn’t match the official one. Me too, I forgot to include the delay of the sound… …according to the official solutions, there was only one team who got this problem right, and only for two submissions :) Good luck in the finals!

    Reply
    1. Psyho

      I’m pretty sure that more teams fell into this trap and there many more of us. That was a really fiendish task :)

      And about that team that solved 2 tests. It was possible to solve the first 2 tests with scaling, since the speed was very similar to the one in example. But it’s also possible that they just guessed the result. Either one of those two options or magic, because a working solution should rather easily solve all of the tests.

      Reply
    1. Psyho

      There isn’t much to talk about really. I always treated classes on my university as a waste of time – I studied because I met many interesting people there, and I wanted to have a degree as a back-up plan in my life.

      Near the end of my studies, when pretty much the only thing left was my thesis, I decided that I feel secure enough with my “accomplishments” from competitions. At this point the only question was whether to go for PhD or drop-out asap. It took me a while to figure this out, but in the end I definitely made a right decision.

      Reply
  2. Jakub

    Hi Psyho,
    I have encountered a problem similar to the problem J and I would be really thankful if you could elaborate on the algorithm that you used. Thank you for your answer in advance.

    Reply
    1. Psyho Post author

      Unfortunately, I can’t help you with I (Crowd Control, right?), since I wasn’t the one who solved it.

      As for J, there isn’t really much more to tell. The solution is just a naive SA without any additional tricks except those that I already mentioned. I’m linking to my code. As far as I see, my implementation there uses O(W * H) algorithm for score change calculation and is pure HC.

      Reply

Leave a Reply

Your email address will not be published.