Interesting Problems: Unity from Deadline24

Intro

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.

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 :)

TCO 13: Marathon Finals, part 4

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.

TCO 13: Marathon Finals, part 3

Part 1 Part 2 Part 3 Part 4

Current Status

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.

TCO 13: Marathon Finals, part 2

Part 1 Part 2 Part 3 Part 4

Multibase Solution

It’s 11:30, we’re 2,5h into the competition and I’m now absolutely forced to do the multibase strategy. No more running away. And I still have absolutely no clue how to do it. If something looks way too complex, it’s a good idea to try and split it into smaller parts. In this exact situation, I came up with the following subproblems:

1. Which worker should build the base
2. Where it should be placed
3. When it should be placed
4. When I have more than 1 base, how should I manage the workers
5. How many bases I should build

Now I’m looking for the simplest way to accomplish each of those subproblems. First of all, let’s assume I’m trying to build at most 1 base at a time. (1) is pretty trivial. Let’s build it with any worker that can do it. Since there’s a constraint that only worker that doesn’t carry any resources can build the bases, let’s use only those. And if all of them are busy with carrying resources, just wait for one of them to be free. (2) is the scary part, so I just imagine that it isn’t here and I’m moving on with my list. The simplest solution to (3) is to build it as soon as we can (we have resources) and build the bases only after I have build all of my workers. Remember that in each simulation I know how many workers I’m going to get. For (4) I can just move each of my workers to the closest base. My intuition is that the workers will “manage themselves” after some time. It’s definitely far from perfect, but on the up side, I already have that implemented, so this is an ideal solution. (5) is even more trivial, because I use the number of bases as an input to my simulate() function and I’m assuming that I’ll just iterate over all possible combinations of workers and bases.

TCO 13: Marathon Finals, part 1

Part 1 Part 2 Part 3 Part 4

Disclaimer

Small warning first. This turned out to be a very long post. Mostly because, I tried to put here all of the important information, so that you can have a full picture of how does it feel to compete at the finals and at the same time have a peek at my thought process during those very long twelve hours. And for people who had never heard of TopCoder’s Marathons before – this is an algorithmic contest where your task is to solve one very hard problem for which there’s no polynomial-time optimal solution. We don’t have to use any APIs, we’re only submitting the code that is remotely executed. And the data (tests) that are used to test our solutions are almost always artificially generated and we’re provided with the generator itself – we just don’t know exact tests that are going to be used. And that is all you really need to know.

The origins for this post are pretty simple. I always thought that those regular “Post your approach” threads were telling only half of the story. The other half is obviously how people are coming up with those mentioned approaches. And since for me, the road itself is far more important than the goal, I wanted to shed some light on that process. My goal here is provide you with a very comprehensive portrayal of what’s going through my mind during the competition. And finally, going with the problem from the finals has many advantages – the contest duration is much shorter, so I can provide more details and the time management is significantly simplified since there are no real-life distractions.