Since you’re here, you probably heard about the 24h livestream (YT mirror) that I did. In short, I was unofficially participating in Marathon24 finals. During the contest, finalists had no access to the internet, so I was able to freely stream my performance without worrying about that someone will freely watch it and use any of my ideas.
I decided to write a short postmortem in order summarize how did it go. If you’re trying to decide if it’s worth watching it, this thing might help you. And if you’ve seen it (or some parts of it) already, this will give you much more insight into all of the problems that I encountered.
The TL;DR version is: I was very distracted throughout the whole stream and overall my tempo was rather sluggish. Despite all of this, I still performed quite well and commented on all of my actions.
It just struck me that I posted everywhere about the 24h livestream that I’m doing, except my very own blog.
Since there are so many details already scattered around the web, I’m just throwing the important links:
- Date – 28/11 Saturday 9:15 AM GMT+1 to 29/11 Sunday 10:15 AM GMT+1
- Twitch Stream – streaming will happen here
- FB event – save the event date, invite people, etc
- Twitter – I’ll use twitter for major announcements; you can also tweet me during the stream if you have any questions (apart from using chat of course)
- Boring Interview – honestly, it’s not that interesting
And if you need a little bit more convincing in order to see the livestream. Mimino wrote 5 pretty solid reasons why you should seriously consider doing it.
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:
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.
I have been competing in various programming contests for the past 10 years. A lot, if you ask me. But, more importantly, I have competed in quite a few different kinds of contests. My adventure started with classic algorithms, and later I switched to optimization problems. Currently I compete mostly in machine learning contests (as a part-time job) and I also do some for-fun contests.
Considering that there aren’t too many people with such broad experience, I thought I’d write a (relatively) short summary of popular types of programming (algorithmic?) contests. This is not a complete list – instead I’m focusing on the ones that are most popular and (in my opinion) most useful.
The structure is type-oriented rather than site-oriented. This means that rather than flooding you with some random sites with an added description, I organized everything into categories and combined sites/contests with similar characteristics. Since some of the sites offer several types of competitions, I had to list them several times.
Ideally, if you’re confused or just curious about the whole world of competitive programming, this should give you a comprehensive overview of the subject.
And yet another post not related to programming.
Some loosely-related stuff about my laziness:
- I wrote a short story about myself for TC. It’s supposed to be fun to read, rather than being informational. I believe I actually made a pretty good job with that, although my standards for such things are set quite low. So don’t expect too much :)
- I still remember about the tutorial for simulated annealing. I actually started writing it a long time ago. I had everything planned out, but in the middle I decided to make it a bit bigger. And add some pictures. And add some animations. And add some code specifically written for the tutorial. And add some analysis about the temperature scheduling. And add a ton of examples from the past contests (i.e. working examples, no theoretical bullshit). And then I searched for some comprehensive articles about SA. But there are none. Literally nothing that I would find good enough to recommend. To anyone. So I’m still doing it (yay), but it will take quite long to write (boo).
- In fact I have several drafts in a near-finished state, so you may expect something posted soon.
- At the same time I’m going to compete in World Puzzle Championship next week (where I once again will fail to place in the top ten), and then I’m going to Japan for some sightseeing, so probably the above point is false.
- But I love working during traveling, so maybe it isn’t!
- I also have a plan for a series of articles about competitive contests (summary of different programming competitions, what’s the point of them, what skills do they develop, etc.)
- More stuff that I forgot about.
- Oh, I updated “About” section, but if you really want to read anything interesting, better read that TC story (the link at the top).
This is going to be a slightly different post than usual. Recently I was asked to construct some diagram puzzles (which are a subgenre of logic puzzles) for a Polish newspaper. Since not all of them are going to get printed I thought that I might as well put them here, so my effort won’t get completely wasted.
A small introduction in case you’ve never seen the diagram puzzles before: Puzzles are generally printed and solved on paper, although it’s fine to solve them in paint or other simple graphics software. Puzzles have only one solution, and it should be possible (and certainly it is with my puzzles) to solve them using so-called logical reasoning, which generally means that the puzzles can be solved without using eraser and/or magic. So it’s like Sudoku (which is an another type of diagram puzzles), but it’s actually fun to solve.
All of the 3 diagrams are Star Battle puzzles. Rules for the lazy: “Put stars into some cells of the diagram, so that every row, column and bold region have exactly two stars. Stars can’t touch other, not even diagonally.” The first two puzzles should be rather easy, but the third one should be a decent challenge for an experienced solver.
Planned SA tutorial takes forever to finish, so I decided to write a short post about the problem that I solved yesterday, while looking through past tasks from Deadline24 contest. The qualifications for this contest are very similar to Challenge24 and IPSC – they only give you inputs and they only want your outputs in return.
One task looked particularly interesting – it’s a direct adaption of something that is known as a dissection puzzle and it’s a type of diagram puzzle you can encounter during the WPC. The rules are very simple, you are given a shape on a grid, and your task is to divide (dissect) it into few smaller ones in such way, that each one of them looks the same. Usually rotations are allowed, but reflections are not. The ugly image on the left, shows an example of a solved puzzle. In this particular problem, the size of those small shapes is given. If you want to read the full problem statement you can find it here, but you don’t really need any more information.
If you have no slightest clue how to solve such problem, then let me assure you that everything is fine with you, since as far as I know (although there’s a small chance that I’m wrong) everyone solved this by hand during the contest.
This post will show you how to solve it in a very simple (conceptually), yet a bit unconventional way.
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 :)
Part 1 Part 2 Part 3 Part 4
This is the last part, and it contains all of the random thoughts that couldn’t be included earlier without breaking my chronological theme. The idea here, is to give you some additional perspective on this 10K-long write-up.
Each section is completely separate and they are listed in no particular order.
Part 1 Part 2 Part 3 Part 4
While I was doing all of the tweaking, the situation that arose on our leaderboard was quite interesting. ACRush was steadily climbing up through the ranks and at 16:45 he made a submission which suddenly puts him right behind me – my lead shrinks from 10%+ to something between 2% and 5%. On the other hand no one else seems to be doing better. The strangest part is that wleite hasn’t submitted anything since 14:40 – I have no idea what could be the reason, especially since he’s not the person to hide his best submission till the last seconds. And he was still in 3rd place. Everyone else had low score, and all of the them rarely submitted anything, so I assumed that they just took an approach where they are implementing something complex right from the start (which is completely opposite of what I was doing). To sum things up – I couldn’t feel any less confident about my temporary first place than I did.
Between one batch of local tests and another, I tried to come up with some more advanced strategies, than the silly one that I was currently using. One thing that had me worried, was that it’s quite probable that I’ll run out of all the small things I can do to improve my score, before the contest finishes. In other words, I thought the potential of my solution (simulating a lot of different greedy strategies, without using any partial results) was pretty low and it’s quite probable that I’m going to hit the dead end 1-2 hours before the end of the contest. I’ll be too tired to rewrite half of my code and I won’t have enough time to properly test it, which should be my top priority considering that I’m making a ton of bugs throughout this contest.