Facebook Hacker Cup 2020 Qualification Round Solutions

29 July 2020

Programming

3 min.

503

Questo articolo è disponibile in italiano

What is the Facebook Hacker Cup?

The Facebook Hacker Cup is a competition for programmers promoted by Facebook worldwide. The aim of the competition is to find the best programmers in the world to whom to pay cash prizes. The final winner will also win the cup.

The problems proposed during the Facebook Hacker Cup rounds are typical programming problems that a programmer may have to solve in real life: many times it is not difficult to write an algorithm, test it on the sample input and verify that the output produced is correct. Each problem in fact provides two text files as example input/output with which to test the program before submitting it officially. At the moment of submission, instead, a longer input is downloaded that is needed to produce the final output, but no more than six minutes must elapse between downloading the input and sending the output.
Here comes the best thing about the Hacker Cup: a correct algorithm may not be enough to produce the full output required by the problem if it has not optimal complexity in time! An algorithm with exponential complexity is good for small inputs but not for large inputs (and in reality it is the second case to be predominant).

The algorithms must not only be correct, but also efficient.

As regards the programming language to use, there is absolute freedom as long as a compiler or interpreter for that language is publicly available.

It starts with a 72-hour qualification round where 3, 4 or 5 problems are proposed.
Participants who have solved at least one problem correctly pass to the first round and to enter the second round a minimum score must be obtained (each problem is associated with a score for a total of 100 points for each round).
From the second round the first N participants pass the round and here comes into the game the penalty, i.e. the sum of the time taken to send the various answers.

For all other details please refer to the official page.

Qualification round 2020

Travel Restrctions (10 points)

You have N cities, each of which can allow or block incoming or outgoing flights. Determine whether you can travel between cities for each pair of cities.

Problem statement – My solution (Python)

Alchemy (15 points)

N stones that can be of type A or B must be fused together to produce a definitive stone. Fusions can be made if you have a triple where not all the stones are the same. Determine if given a set of stones you can fuse them all together.

Problem statement – My solution (Python)

Timber (21 points)

In a forest there are trees that can be cut down and form a “timber interval”. These trees have a specific position and height and can be dropped to the right or to the left. Calculate the longest interval that can be achieved.

Problem statement – My solution (Python)

Running on Fumes Chapter 1 (16 points)

A delivery man has to go from one city to another and on the way there are other cities he will necessarily have to cross. The vehicle on which he travels has a maximum fuel capacity and the man has to decide in which cities to refuel in order to complete the journey with the lowest possible expense. Calculate the minimum cost to go from the first to the last city.

Problem statement – My solution (Python)

Other solutions

All the previous solutions, along with some of the past years, are available in my GitHub repository.