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.
Before the Finals
This TCO was my 6th Marathon finals. With each new year it’s getting harder to stay motivated. It’s not that it’s boring, because it’s very far from that. In fact, MM finals is one of the most thrilling (when you’re the one competing) type of contests I have ever attended. But it loses some part of its magic after so many times. Another factor is that I always feel a lot of pressure regarding my performance, mainly because I really believe that I incredibly overperformed during the past finals, but for some reason my mind doesn’t accept this as a fact and it still has a very high expectations of me. In addition to that, this year I had strange health issues. The short story is that I had some flu-like symptoms that spanned over few months, during which I visited a lot of doctors, had a lot of examinations and every single diagnosis was that there’s nothing wrong. Not the best feeling in the world. So basically, my morale hit the new time low just when the TCO was happening.
Ok, enough of my middle-aged crisis rambling and let’s move onto the finals :) First of all, let’s explain the differences between the regular two-week MM and the 12h finals. The first difference is that it’s loud. Very loud. Unless you’re already focused, it’s very hard to concentrate. The other is that there’s no “creative downtime” during which you come with all of those brilliant ideas. While in theory we’re allowed to move around the arena (the big room where all of the exciting TCO-things are happening), I don’t think anyone uses this privilege. Probably the only place where you can get some rest is a toilet. And the last difference is that what normally is a competition where you race against yourself, changes into race against the others. During 12h you’ll be nowhere close having a good solution and the same goes for your opponents, so you have to set your goals realistically.
And that concludes the long and unnecessary introduction :) From now on, I’m going to explain everything that was happening chronologically – this is really the only way in which I can thoroughly explain why and what I was doing. You are free to take breaks from reading this and think about the problem on your own. Or if you have some more time, you can write your own solution.
The contest starts with the 30 minutes preparation, it’s an added time where you can download and install some stuff that is not on our machines – everyone finalist gets the same machine with the same preinstalled software. The only thing I need is a pthread library that apparently is not included in MinGW distribution that we have on our computers. It was surprisingly hard to find a working lib on the net, since more than half of the links were dead. It took me around 10 minutes, I also checked that everything works correctly and then I was just awaiting the start of the competition and trying to get “in the zone”. Short break for competitors announcement and the only thing that’s left is to wait for the actual contest to start.
Let the Marathon Finals Begin
The competitions starts exactly at 9:00, everyone opens the problem statement. Now if you haven’t seen the problem yet, please read it now here. You don’t have to fully understand it, just the general idea what we have to solve is enough. At least in most cases, during my first reading of the problem statement, I’m only trying to grasp the basic idea.
Around 15 minutes later I’m done with the reading. My first impressions:
- It’s very similar to TCO13R1 problem – you have to manage several workers on the grid and people who competed there might have a bit of advantage here.
- This is the problem where every bit of information is given to you. This is absolutely great for me, because I’m (based on my past competitions) very good at code optimization, and I’m usually the first guy to use all of the available execution time.
- It’s pretty clear that the decision when and how build workers/bases is insanely hard and it’s just plainly impossible to make educated guesses here. This means that in order to test what numbers are best, I will have to make full simulations till the end with different parameters (number of workers/bases to build, maybe something more).
- I made some quick calculations in order to estimate how many simulations I’ll be able to do in the worst case. I assumed that I’ll have to make a single BFS in order to gather one resource. The grid is NxN, so we have N2 BFSes (each BFS should gather one resource point and we have at most N2 of them) and each one of them takes N2 time. Maximum N is 60 and 604 is roughly 13M. We have 10 seconds available for each test, so in the worst case realistically this should give me at least few dozens of simulations. This should be enough to test some randomized greedy approaches with various strategies.
- There are lots of additional movement constraints. It seems that it’s easy to make a bug (and I hate debugging since it kills my motivation – this is especially important during the short finals) and it will be hard to find it later – it’s rather obvious that the programs will be rather large with complex logic. So my priority here is to find a way to design a solution that will be improved incrementally in very small steps – this usually reduce the amount of time spent on debugging and it’s a great way for staying motivated – a very important factor considering how I felt.
- Linked with above, I decided to write a simple greedy solution that uses only initial worker and base. I believe there’s only one such solution so feel free to think about it.
- The most important movement constraint is that resources essentially block the worker movement and the only way to remove them is to gather them. The problem is that you can’t drop/discard the resource. Which means it’s not possible to “power through” the map. This constraint alone makes the problem very complex.
At this point I had no idea how to solve the problem efficiently. I spent few minutes thinking about it, but it was very clear that it’s just way too challenging to tackle it right away. But since there’s a nice simple greedy solution that should (after all it’s all guessing, since I had no idea at this point how it’s going to look like) nicely build into the final solution – whatever it may be.
I started coding. I believe it was somewhere around 9:25 – 9:40. First I set up the do-nothing solution, then I wrote the code that connects java visualizer with my solution and finally I configured my offline tester with the problem. Everything works. The first algorithm design decision I made was that I’ll need simulate() function that will perform some greedy-like algorithm based on some parameters. If it turns out that it’s not enough I’ll rewrite it later. On the plus side, it really simplifies the thinking about the problem, because the part where I choose strategy is different from the part where I execute it. Of course, so far I have no strategy at all :) Next things on my list are just standard “solution storing” stuff and then finally I can work on my basic trivial solution.
If you haven’t figured it out so far. The trivial solution is to always gather resource that maximizes resource_value / distance_to_base. It’s definitely not optimal because after each removed resource distances are changing. It may be worthwhile just to gather some closer low-value resources in order to reduce the distances to higher-valued ones. But well, it’s again a complex problem and I don’t want to get stuck solving a very hard problem when I have no idea how significant it’s going to be in my final solution. So for now, I’m just ignoring this issue.
When it came down to implementation, I failed miserably. Around 10:00 I should have everything working, but unfortunately I was getting errors that my worker goes into cells with resources even though it should be already en route to base. I did a “code inspection” of my solution, which is essentially just rereading every bit of a code you wrote. I haven’t found any mistakes. I’m usually catching most of errors in that way – it’s an easy and a great way of manual debugging, but this only works if you have a consistent coding style and you build your solution incrementally with frequent runs. I’ve put a lot of various debug output into my solution and I did a manual step-by-step analysis. But after 20+ minutes I still couldn’t find any mistake. I rarely spend more than 10% of my time on debugging. Usually it’s much less, so at this point I was already frustrated. Finally it took me around another 20 minutes to notice that my mistake was “just” a flawed algorithm. Essentially my BFS generates the distance table. But I construct it in a way that I’m allowed to step on the resource cell, and that has to be my last move. While reconstructing the path I forgot that except that single resource I’m harvesting, I’m not allowed to step on them. Pretty glaring and noobish mistake. But hey, I have to live with it for another 10 hours, so I have to keep going. I add a simple fix (line #273: mp[nx][ny] == 0) and I submit my first code.
Originally I wanted to show you the scoreboards I was seeing at specific points of time. Unfortunately in order to recreate them I’d have to rerun all of the solutions (not only mine) on the very same set of provisional tests. And there would be some additional problems with scaling of the time limit, which I’d have to do manually for each of the solutions. I would also had to handle infinite loops and crashes. And you would never see this post :)
At this moment only three of us (me, wleite and chokudai) had some reasonable number of points and all three were close to each other. Notably, both of them submitted their solutions 30 minutes before I did. But honestly, at this point the scoreboard doesn’t tell too much. First of all, many competitors have a different strategy, and not everyone tries to implement a simple naive approach, and many others won’t submit it, even though they have a working solution. So basically unless I would show up in the bottom half of the leaderboard, those standings doesn’t give away any kind of information that I could use at this point.
So I’ve finished up my greedy approach. It seems it works or at least my local scores are not showing any errors. And now I have the confidence that I correctly understood the problem – and this is important, because it gives me one less thing to worry about. The price is that I’ve already “lost” nearly 2 hours and I still have no idea how to solve the problem efficiently. And I need a new plan. I decided to reread the problem statement – just to make sure I’m not missing any kind of crucial information. The fragment that I almost entirely omitted was the generation process of workerCost/baseCost. It turns out that this fragment “In other words, the base costs approximately form a geometric progression with a multiple of bpw and the sum of this progression constitutes approximately the bmul-th part of all available resources.” is all I really have to know, because it tells me that most probably I will never ever need to use all of the available workers and bases.
Anyway, rereading didn’t provide me with any a-ha moment – I still had no idea what I’m going to do. So my choice was either to spent another hour thinking (possibly not coming up with any idea and loosing my motivation) or to build any kind of more advanced solution that will use multiple bases and workers. What’s important here is that I’m trying to effectively manage my time. I figured out, whatever the final solution will be, I’ll need code that will be able to handle multiple workers and bases. Due to the number of movement constraints, it’s easy to make few bugs here and there. And in general, the more focused you are, the fewer bugs you make. Thus, it’s best to write error-prone parts of your code, while you’re still in good shape. And as a bonus, you feel you’re getting closer to your goal, by essentially procrastinating coming up with a decent approach. Good enough.
So, I have a plan. Time to execute it. Again, I want to improve my solution with as small steps as it’s possible. That way, when I’ll have any kind of bug, I’ll know where and how it occured. I figured out that adding multiple workers should be pretty easy, since all I have to do was to build them (and it’s trivial to notice that if you have one base, you always want to build them as soon as you have money for a new one – with many bases it’s a bit more complex because you might want to wait for a new base, although it’s a rare case) and make sure that they gather different resources. Of course, there’s this decision “How many of them I should build?”. But I already solved it before – my idea was to try to solve each test with a different number of workers and save the solution which gives the best result. All I had to do was to add a parameter to my simulate() function that described how many additional workers I want to build and I had to run it with all possible values. 25 minutes later, and my 2nd submission is ready – I get a nice and round score of 950000, which means that no one else is using multiple workers yet and my solution crashed/gave invalid result on 5 out of 100 tests. The wonders of relative scoring :)
Now my first priority is of course to fix the bug, so back to my favorite code inspection process. Turned out one of tables was just too short and failed all of the tests where the size of workCost was 20. Surprisingly enough there were only 5 such tests, even though the expected number of them is a bit higher: 100/11. Submission #4 is another bug fix and it finally puts me with a perfect score. I decided to delay a bit my implementation of multi-base solution and started having a bit of fun with my greedy function that chooses the next resource. The reason why I wanted to that now was because I thought that it’s quite probable that I’m keeping that function for the rest of the contest and it’s a good idea to tweak it now while the execution time of my solution is still very low (below 0.2s on most tests), because as soon as I add multiple bases, I’m going to use all of the available time which means that I’ll have to wait a lot more for my local tests to finish. The first idea was to give more value to resources that are close to base, so that those low-value resources that are near, but they are blocking fast routes are getting removed quicker. My function changed from resource_value / distance_to_base to resource_value / (distance_to_base - X). I didn’t want to do anything complex here, I just tried to see if there are some very simple changes that can improve my score. I test few different numbers for X and I leave it at 0.5 which gives me a 1% improvement and this was my 5th submission. #6 was just a small modification where I made sure that I’m not trying to mine any resource if I’m not going to return with it to base on time. Another 2% improvement.