#TuentiChallenge6: Compilation of solutions and writeups

Publicado el 21/6/2016 por Alfredo Beaumont, Senior Software Engineer

We have compiled some solutions and writeups made by participants that you may find interesting. Hope you like them.

Solutions

Writeups

@Landertxu0 has prepared a complete series of writeups for every problem, you can read them (in Spanish) at:

HMU29: and the winners are…

Publicado el 17/6/2016 por Outreach Committee

Another quarter, another Hack Me Up. The 29th edition of our internal programming competition has just finished at the Tuenti office in Madrid. Bots from the sofa was the theme of this edition, which is why projects were focussed on bot technology.

With 13 projects presents, these are the final results:

  • Super Call Saving Player, the winning project in the Product category. Jessica, Manolo and Rayco made a new awesome player for the call saving functionality.
  • Tuenti Core was the project that took home the Geek Cup. Sergio made a multiplatform development in C# to show the posibilites of the .net framework. Very geek, indeed.

Despite there being only two winning projects, many of those presented were of excellent technical quality and may be implemented at Tuenti for the use of our clients and users. We’ll keep you informed ;)

Congratulations to the winning teams!


Final Challenge in #TuentiChallenge6

Publicado el 16/6/2016 por 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.

Tuenti Challenge 6: Bricks and Bridges write-up

Publicado el 13/6/2016 por José María Pérez, Software Engineer

Hello again! I'm the author of problem 19, Bricks and Bridges (as well as of problems 6 and 15). Here is the write-up of this problem:
 

In this challenge, I tried to create a misleading problem in which things that seem easy are hard and things that seem hard are easy (in the end).

When you encounter the problem, the first thing you find is the requirement to go through all the nodes on the graph, and the fact that you have to bring down all of the bridges. In order to bring them down, you have to cross them, so instead of finding a hamiltonian path, you need to find a eulerian path (with some quirks).

So, for each level, it is possible to solve it if, and only if:

  • All nodes are connected
  • A eulerian path exists (there are a maximum of two odd-degree nodes)

How do you find out the degree of the nodes?

x[1] * STEPFORCE[1] + x[2] * STEPFORCE[2] + ... + x[n] * STEPFORCE[n] = BRIDGE_TOUGHNESS with x >= 0 and then BRIDGE_DEGREE = sum(x)
(It could be interesting to use some papers but dynamic programming is more than enough for this task).


We are only looking for a single even-sum solution and/or a single odd-sum solution (to see if the node degree could be odd and/or even).

There are 3 possible outcomes of this step for each bridge:

  • It has no solution (all solutions include a negative x or gcd(stepforces) does not divide its toughness): The level is impossible. For example, a bridge with toughness 3 which only has a stepforce of 2, or the same bridge with stepforces 5 and 2.
  • All solutions have an even OR odd BRIDGE_DEGREE. Add the corresponding degree to each node the bridge connects (it really only matters if it’s even or odd)
  • It has solutions with an even AND odd BRIDGE_DEGREE. (We’ll call this bridge a ‘BOTH bridge’).

Once you reach this point, you can try to solve the problem. To do this, you can check all possible combinations of oddness for each BOTH bridge, and just apply the eulerian path rule:

  • There are 2 nodes with an odd degree, the path goes from one of those to the other.
  • There are 0 nodes with an odd degree, the path goes from any node to itself.
  • There are more than 2 nodes with an odd degree, the path does not exist.

(Remember that it’s impossible to have an odd number of odd degree nodes, as, in this case, there would be a bridge going nowhere)

Unfortunately, there is a big problem with this solution. Its complexity is exponential for the number of BOTH bridges, as you need to check each possible oddness (even or odd): 2*2*2*2*…*2 = 2^(number of BOTH bridges).
Taking into account the sheer amount of BOTH bridges, this is not feasible. Thankfully, however, there is a shortcut:

Shortcut:

After processing the diophantine equations, you mark all the bridges in the graph with EVEN, ODD or BOTH tags regarding each diophantine solution. To solve the problem, you need to count the degree of each node and then count the nodes that have an odd degree (EVEN bridges add 0 to its connected nodes, ODD bridges add 1, and BOTH bridges add 0 or 1, whichever you want)

If you remove the EVEN and ODD bridges, you get a graph consisting of nodes with a partial degree connected by the remaining bridges (those with the BOTH tag; remember that there could be several connected subgraphs) and nodes with a fully calculated degree, which are not connected to any other node.

At this point, you have to minimize the count of odd degree nodes and check that there are no more than two of them (if there are more than 2 odd-degree fully calculated nodes, you can stop now, as the scenario cannot be solved).

In order to minimize the count of odd-degree nodes for all the partial-degree connected subgraphs, you just need to add each subgraph’s partial degrees together and check if this is EVEN or ODD for each of the subgraphs, which is O(n).
This is the proof for each connected subgraph:

Problem: Fully connected graph with nodes tagged with either 0 or 1, all arcs could add 0 or 1 to both ends, minimize the count of odd-degree nodes.
Solution: sum(degrees) % 2

Proof 1:

  • A 0-arc leaves both ends as they are
  • A 1-arc switches both ends (from 0 to 1 and from 1 to 0)
  • You can 'move' a 1-node around by fixing 1-arcs, and when it's directly connected to another 1-node, you can turn both of them to 0-nodes with a 1-arc
  • In this way, you can turn 1-nodes into 0-nodes by pairs

Proof 2:
You can fuse two nodes together by adding their degrees and removing all the bridges that connect them directly:

  • If both of them were 0, you would use a 0-arc, thus maintaining the number of 0-nodes
  • If both of them were 1, you would use a 1-arc, thus reducing the number of 1-nodes by 2
  • If one were 0 and the other were 1, you would use a 0-arc or a 1-arc, depending on where you would like the 1-node to be, but maintaining the number of 1-nodes

To answer your unspoken question, yes, I tried to place the problem in Alice in Wonderland’s world, but it felt too forced.

And so ends my contribution to this year’s Tuenti Challenge. I hope you liked it :)

Tuenti Challenge 6: Seat change! write-up

Publicado el 10/6/2016 por José María Pérez, Software Engineer

Hi there! I'm the author of problem 15, Seat change! (as well as of problem 6). Here is a small write-up of this problem: 

When we change seats at Tuenti, a friend always jokes about the tea party scene in Disney’s Alice in Wonderland and, in the past, I've worked with matrix multiplication... why not combine both of them in this challenge?

In this problem, you have chairs, probabilities of going from one chair to another chair and a number of seat changes. If you can recognize a Markov Chain in this problem, you’re spot on. If you did not recognize it, don’t worry, the math is pretty basic:

Suppose that you organize the probabilities of going from one chair to another after one seat change in a matrix, where rows are starting chairs and columns are ending chairs. If you multiply that matrix by itself, you will get the probability after two seat changes.
In fact, the problem is asking you about the index for the max element in a row of matrix^number_of_seat_changes, using integers to maintain the precision.

Multiplying two square matrices has a complexity of O(size³) (less if you use certain algorithms, but this is not the objective of the problem) and there are some optimizations that are useful:

Depending on whether N is even or odd:
    matrix^N = (matrix^(N/2))²
    matrix^N = (matrix^((N-1)/2)² * matrix
This reduces the complexity of the number of matrix multiplications from O(N) to, O(log2(N)) (at the expense of storing intermediate matrices), and it was intended to be needed in order to solve the problem.

Another useful optimization is breaking the connection matrix into its connected components and computing them separately. For example, if you have N chairs in two connected components, one of them of size M, the complexity of the matrix multiplication is reduced from O(N³) to O(M³) + O((N-M)³). As the matrices do not change between tries, you can check if this optimization is useful before coding it (Hint: it is). It also has the benefit that you may not need to exponentiate both matrices to the same exponents.

With those two optimizations, and caching the intermediate results, you could solve the problem with the hard input in a reasonable time (my solution does it in less than one minute).

Well, that's it for today. I hope you liked it and remember:
We're all mad here.
- Lewis Carroll, Alice in Wonderland

Pages

Siguenos