Final Challenge in #TuentiChallenge6

Posted on 6/16/2016 by Jose María Palacio Lardin, Software Engineer

In this problem, we are asked to arrange some calls in order to get as many stars as possible. You can read the statement here. This is an optimization problem: instead of asking for the optimal answer as usual, we can submit as many solutions as we want and keep the one with the highest score.

There are plenty of possible approaches for this problem and it’s not easy to decide which one to use, as it’s hard to guess the effectiveness of an approach without actually implementing and experimenting with it. We will evolve from a simple solution to a good one during this write-up, serving as a step-by-step summary of the process that we went through when we developed our solution.

As we don’t need to worry about our initial score, let’s start simple: by getting a correct solution. The first greedy algorithm that comes to mind is to pick the call which gives us the maximum amount of stars while there are unassigned calls. To implement this, we will need a way to check if a call fits in a pop and what its starting time would be. After reading the statement carefully one more time, we realize that a call can only have a maximum delay of 40 and, luckily, the average duration of a call is not very long. This simplifies things a lot, because we can check if a call fits in a pop simply by trying all the possible delays. We can represent each pop as an array of integers indicating the calls in progress at a given moment in time, which allows us to insert a new call, delete a call or get the starting time of a new call in time O(duration of the call).

Our greedy calculates the starting time and the stars for every call in every pop at each step, and the number of steps is potentially the number of calls. Our first impression is that this seems very expensive. Indeed, after implementing it and running it for some minutes, it still has plenty of steps left to finish. We have to start optimizing:

  • Precalculate the stars for every call and pop with delay 0 in order to avoid computing distances.
  • For every call c and pop p, we can cache the amount of stars obtained by establishing c in p. We can check if this number is smaller than the current best to filter.

After these optimizations, our program runs substantially faster: after 25 seconds we get a valid solution with score 32191.

What can we do to improve our solution? If we look at our algorithm again, we can see that there are a lot of ties (after all, we only have 4 possible values of stars if we discard the 0). When two calls (or the same call in two difference pops) have the same number of stars, can we look at something else to decide which one is a better choice? Our idea is to choose the one that places least “stress” on the pop: we want to maximize the free slots in the pop during the call. Introducing this tiebreaker sees our score increase to 32750.

However, there are still a lot of ties, so a new idea springs to mind: we can simply order all the calls before starting our greedy with some criteria that don’t depend on the current status, and the ties will break naturally. While we are at it, we can order the pops too! It seems like the best way of ordering the pops will be in descending order of their capacity, but the calls are harder. There are a few things that seem important: the duration, the finishing time and the density of a call (ideal stars / duration). After experimenting with some orderings, we can see that the best thing we can do for our greedy is to minimize duration, minimize starting time and maximize density, in that order of priority. With these tweaks we get a score of 35030.

Even though our score is quite good, we are not satisfied with it. After playing a bit more with our greedy algorithm, we don’t see anything that improves our score, so we decide that it’s time to apply some form of local search. We encounter a big problem though: there isn’t a simple way to transition from a valid state to another. After some time thinking about this with no results, our mind goes back to the greedy algorithm. Given the same input, our greedy always establishes the same calls in the same order, but what if we skipped some of them? Perhaps skipping a call with 5 stars would allow us to later establish two calls with 4 stars, improving our overall score. Indeed, after toying a bit with the algorithm and ignoring a few random calls, we can see that our score changes, and is sometimes higher than 35030. This suggests something interesting: perhaps we can destroy part of our solution and apply the greedy algorithm starting from the new partial solution. Destroying part of our solution means removing some calls from some pops, which seems very easy with our data structures. The only thing left to decide is which calls to remove. It seems like a good idea to remove an interval of continuous calls: this leaves a big empty area for our greedy algorithm to work with.

After some time implementing all of this we get our reward: if we remove around 50 calls, an iteration takes about 2 seconds and every few iterations we get an improved score! And the best thing is that we can reuse our cache for the next iteration if we are careful and invalidate the correct positions after removing the calls, which makes things orders of magnitude faster: with this approach, an iteration takes an average of 6.4ms. After seeing this, we are almost ready to leave our program executing for the night. Before that, though, we introduce some changes to try to avoid getting stuck on a score:

  • Add noise to the tiebreakers
  • With some small probability, remove non-contiguous intervals of calls instead of contiguous ones
  • When reconstructing the solution, we treat the removed calls as we would any other unassigned call. With some small probability, ignore the removed calls completely until all the others unassigned calls have been tried
  • When removing calls, try a few options; removing calls from a single pop, from half of the pops, or from all the pops
  • Introduce randomness in all the hard-coded values, like the number of calls removed per iteration, number of pops from which to pick calls to remove, etc.

Now we are finally ready to execute the program. Here is an evolution of the score over time (in seconds):

After 5 days, we get a solution with a score of 36053. Five days is a lot, especially during a contest that only lasts for seven days, but as you can see in the graphs our algorithm improves the solution at a logarithmic speed: it took less than one day to reach 36000 and roughly an hour and a half to reach 35900, so it would have been a good option even with the time restrictions of the contest.

Our solution is not the optimal one but our algorithm slows down too much to keep going, so it suggests that we are close to it. We may, however, be stuck in some local minima that our greedy reconstruction approach cannot overcome. We gave up at this point, though.

We hope the four contestants who reached this problem had fun with it, and if you are not one of them you can always try it now! We have published the submission validator that we used during the contest, so you can use it to validate and get a score from your solutions. If you beat us, have some idea to improve our solution or you used a totally different approach, don’t hesitate to share it with us.

Follow us