Soluzioni Qualification Round Facebook Hacker Cup 2020

29 Luglio 2020

Programmazione

3 min.

502

This post is available in English

Cos’è la Facebook Hacker Cup?

La Facebook Hacker Cup è una competizione per programmatori promossa da Facebook a livello mondiale. Lo scopo del concorso è trovare i migliori programmatori al mondo ai quali corrispondere dei premi in denaro. Il vincitore finale inoltre si aggiudicherà la coppa.

I problemi proposti durante i round della Facebook Hacker Cup sono tipici problemi di programmazione che un programmatore può trovarsi a risolvere nella vita reale: molte volte non è difficile scrivere un algoritmo, testarlo sull’input di esempio e verificare che l’output prodotto è corretto. Ogni problema infatti mette a disposizione due file di testo come input/output di esempio con il quale testare il programma prima di consegnarlo ufficialmente. Al momento della consegna, invece, viene scaricato un input più lungo che serve per produrre l’output definitivo, ma non devono passare più di sei minuti dal download dell’input e l’invio dell’output.
Qui viene il bello della Hacker Cup: un algoritmo corretto potrebbe non essere sufficiente a produrre l’output completo richiesto dal problema se non ha complessità in tempo ottimale! Un algoritmo con complessità esponenziale va bene per input piccoli ma non per input grandi (e nella realtà è il secondo caso ad essere preponderante).

Gli algoritmi non solo devono essere corretti, ma anche efficienti.

Per quanto riguarda il linguaggio di programmazione da usare c’è libertà assoluta, purché sia disponibile pubblicamente un compilatore o interprete per quel linguaggio.

Si parte da un round di qualificazione della durata di 72 ore dove vengono proposti 3, 4 o 5 problemi.
Passano al primo round i partecipanti che hanno risolto almeno un problema correttamente e per accedere a secondo round bisogna acquisire un punteggio minimo (ad ogni problema è associato un punteggio per un totale di 100 punti per ogni round).
Dal secondo round passano il turno i primi N partecipanti e qui entra in gioco la penalità, ovvero la somma dei tempi di invio delle varie risposte.

Per tutti gli altri dettagli rimando alla pagina ufficiale.

Round di qualificazione 2020

Travel Restrctions (10 punti)

Si hanno N città, ognuna delle quali può permettere o bloccare i voli in entrata o in uscita. Stabilire se si può viaggiare tra una città e l’altra per ogni coppia di città.

Testo del problema – La mia soluzione (Python)

Alchemy (15 punti)

N pietre che possono essere di tipo A o B devono essere fuse insieme per produrre una pietra definitiva. Le fusioni si possono effettuare se si ha una tripla dove non tutte le pietre sono uguali. Stabilire se dato un insieme di pietre le si può fondere tutte insieme.

Testo del problema – La mia soluzione (Python)

Timber (21 punti)

In una foresta ci sono degli alberi che possono essere abbattuti e formare un “intervallo di legname”. Tali alberi hanno una posizione e un’altezza specifica, inoltre possono essere lasciati cadere a destra o a sinistra. Calcolare l’intervallo più lungo che si può realizzare.

Testo del problema – La mia soluzione (Python)

Running on Fumes Chapter 1 (16 punti)

Un fattorino deve andare da una città all’altra e sul tragitto vi sono altre città che dovrà necessariamente attraversare. Il mezzo su cui si sposta ha una capacità massima di carburante e l’uomo deve decidere in quali città fare rifornimento per completare il tragitto spendendo il meno possibile. Calcolare il costo minimo per andare dalla prima all’ultima città.

Testo del problema – La mia soluzione (Python)

Altre soluzioni

Tutte le precedenti soluzioni, insieme ad alcune degli anni passati, sono disponibili in una mia repository su GitHub.