Facebook Hacker Cup 2016

[Ghehe]

Facebook Hacker Cup 2016

Wat is de Facebook Hacker Cup?

De Facebook Hacker Cup is een jaarlijkse programmeerwedstrijd waarin hackers (efficiënte) oplossingen proberen te bedenken voor bepaalde problemen.

De Facebook Hacker Cup bestaat sinds 2011 en is Facebooks officiële programmeerwedstrijd.

Wanneer is de Facebook Hacker Cup 2016?

Ronde	Start	Duur	Eind
Online Qualification Round	zaterdag 9 januari 01:00	72 uur	dinsdag 12 januari 01:00
Online Elimination Round 1	zaterdag 16 januari 19:00	24 uur	zondag 17 januari 19:00
Online Elimination Round 2	zaterdag 23 januari 19:00	3 uur	zaterdag 23 januari 22:00
Online Elimination Round 3	zaterdag 30 januari 19:00	3 uur	zaterdag 30 januari 22:00
Onsite Finals at Facebook London	3 maart 2016

(Uren zijn in GMT+1)

Hoe kan ik meedoen

Simpel, als je al een facebook account hebt, kan je met dat account je inschrijven voor de Hacker Cup. Inschrijven doe je op https://www.facebook.com/hackercup/register.

Vragen

Het concept is simpel, je krijgt een probleem en daar moet jij een oplossing voor vinden. Je krijgt bij je probleem al een heel simpel voorbeeld van input en output. Als jij denkt dat je oplossing het probleem kan oplossen dan download je wedstrijd-inputdata en haal je die door je programma. De output upload je naar Facebook welke je oplossing zal nakijken en als juist of fout zal beoordelen. Na het downloaden van de input heb je 6 minuten om de output de uploaden, je moet dus zeker weten dat je programma correct en snel genoeg werkt voor je de input downloadt.

Oude opgaven

Year	Round	Problems	Solutions
2015	Final	Fox Blocks Fox Lochs Fox Focks Fox Hawks Fox Locks	Solutions
	3	Boomerang Lunch Scheduling GentrificationFox Rocks	Solutions
	2	Lazy sort, All Critical, Autocomplete strikes back, Fox socks
	1	Homework, Autocomplete, Winning at sports, Corporate gifting	Solutions
	Qual	Cooking the Books, New Year's Resolution, Laser Maze	Solutions
2014	Final	Intervals of Love, Lunch at Facebook, Fortunate Wheels, Tours
	3	Secret Santa, Pizza Baking, Restaurant Chains
	2	Magic Pairs, Hold'em Numbers, Ski Resort Planning	Solutions
	1	Labelmaker, Coins Game, AAAAAA, Preventing Alzheimer	Solutions
	Qual	Square Detector, Basketball Game, Tennison
2013	Final	Archiver, Colored Trees, Minesweeping, Teleports
	3	Digits War, Name the Baby, Greedy Entertainers
	2	Cake Cutting, RoboElection, Permutations
	1	Card Game, Security, Dead Pixels	Solutions
	Qual	Beautiful strings, Balanced Smileys, Find the Min	Soultaker's notes
2012	3	Divisor Function Optimization, Trapezoids, Unfriending
	2	Monopoly, Road Removal, Sequence Slicing
	1	Checkpoint, Recover the Sequence, Squished Status
	Qual	Alphabet Soup, Auction, Billboards	Solutions
2011	Final	Alien Game, Party Time, Safest Place
	2	Bonus Assignments, Scott's New Trick, Studious Student II
	1B	Chess 2, Diminishing Circle, Slot Machine Hacker
	1A-2	Diversity Number, Turn on the Lights, Wine Tasting
	1A	After the Dance Battle, First or Last, Power Overwhelming
	Qual	Double Squares, Peg Game, Studious Student

Andere competities

NWERC 2012 (Vragen/Oplossingen)
BAPC 2012 (Vragen/Oplossingen/Testdata) (Zip-bestand)
Vlaamse Programmeerwedstrijd '09, '10, '11, '12 (Vragen/Oplossingen/Testdata)
Project Euler
USACO Training Program
TopCoder
CodeForces
UVa Online Judge
SPOJ
Google Code Jam
Python Challenge

Zie ook de reacties van Soultaker, kokx en MrHaas in het topic van 2013.

Hackers Wall of Fame

Soultaker - Finale 2011 (laatste 25)

Voorgaande topics

In de voorgaande topics kan je vragen, oplossingen en discussies terugvinden.
Facebook Hacker Cup 2011
Facebook Hacker Cup 2012
Facebook Hacker Cup 2013
Facebook Hacker Cup 2014
Facebook Hacker Cup 2015

[ Voor 100% gewijzigd door Ghehe op 02-01-2016 23:35 . Reden: Ninja-edit: foutje in datum ]

[dcm360]

Met de einddatum van de kwalificatie die nu in de startpost staat zou de duur van de ronde ruim 10 jaar zijn (moet dinsdag zijn namelijk).

En ook dit jaar maar eens kijken waar het schip strandt. Op zijn minst iets goed hebben in ronde 1 en dan is de deelname voor mij wel geslaagd, vorig jaar was dat niet gelukt.

[Anoniem: 691473]

Kun je hier als bezoeker heen gaan(finale)? Kan namelijk niks vinden. Wilde sowieso een tripje maken naar Londen en die dagen komt me redelijk goed uit.

[- peter -]

Wat hier altijd erg belangrijk bij is, is dat de voorbeeld input veel simpeler is dan de daadwerkelijke input. Wel wordt er aangegeven wat de limieten van de input variabelen kan zijn. Het is dan ook slim om daar mee te testen, en niet alleen met de voorbeeld input een brute force methode te verzinnen, die er bij de echte data uren over doet.

[Camulos]

Zal zeker weer meedoen

[mclegodude]

zin in! vorig jaar niet zo heel ver gekomen ivm verhuizing, dit jaar hopelijk ietsjes verder komen

[Camulos]

De kwalificatie ronde is begonnen! (nog tot ongeveer maandag avond, 64 uur as I type)
Succes iedereen

Edit: Snel de challenges doorgenomen, maar ik snap de vraagstelling niet voor vraag 1 Boomerang Constallations. Wanneer zijn ze gelijk? Case #1 is 0, maar Case #2 = 4.

Ik lees waarschijnlijk over iets super triviaals. Kan iemand uitleggen waar ze naar op zoek zijn?

[ Voor 56% gewijzigd door Camulos op 09-01-2016 09:18 ]

[wimjongil]

Je hebt vijf sterren op de volgende coördinaten: (0,0), (0,1), (0,2), (0,3), (0,4). Ze liggen dus op één lijn. Van (0,0) naar (0,2) is dezelfde lengte als van (0,4) naar (0,2) en bovendien hebben ze hetzelfde eindpunt ((0,2) dus). Voor (0,0), (0,1), (0,2) geldt hetzelfde, alleen is hier de lengte 1 ipv 2. De andere twee boomerang constellations zijn vanzelfsprekend.

[vliegnerd]

Is het toegestaan om "eigen" testcases uit te wisselen? Dus niet de "input" die facebook geeft, maar een zelf gemaakte testcase, die ingewikkelder is dan de door facebook aangeleverde?

Of moeten we daarvoor wachten tot na de deadline van deze ronde?

[Soultaker]

In principe mag je niet samenwerken. (Uit de Terms & Conditions: "Competitors must not cheat; all ideas for Submissions must be original, solely the Competitor's, and Competitors may not collaborate on a Submission.")

Moeilijke testcases uitwisselen lijkt me ook samenwerken, want het kost tijd en moeite om goede testcases te verzinnen. Bewaar je testdata dus liever tot ná deze ronde.

[Jeroen Sack]

Ik ben er ook mee bezig, maar dit is wel een stuk lastiger dan google CodeJam, ik kan de example van "High Security" bruteforcen maar doe er bij de example input al 30 seconde over, denk dat ik de echte input daar nooit mee ga halen.

[Camulos]

Inmiddels ook High Security ingeleverd.. pff een paar eigen testcases helpt wel
Uit eindelijke runtime under de 60ms weten te houden (C#).
Qua complexiteit hang ik ergens tussen de O(2N) en O(N^2).

Kijken of ik nog de 3e en 4e ga inleveren

Edit: 3e geprobeerd, time expired (net over de 6 minuten)

[ Voor 12% gewijzigd door Camulos op 10-01-2016 19:57 ]

[Soultaker]

O(2N) = O(N)

High Security kan in O(N) als je een beetje je best doet.

[Qzar]

Heb de eerste challenge geprobeerd. Met de voorbeeld input zat ik netjes op 2 ms execution time maar toen ik mijn uiteindelijke input ging verwerken ging het even niet meer .

code:

C:\Users\Rick\Documents\GitHub\FB\1> node .\app.js
input: 1ms
segments: 0ms
constellation : 1ms
C:\Users\Rick\Documents\GitHub\FB\1> node .\app.js
input: 38ms
FATAL ERROR: JS Allocation failed - process out of memory

edit: typo

[Soultaker]

Qzar schreef op maandag 11 januari 2016 @ 16:34:
Heb de eerste challenge geprobeerd. Met de voorbeeld input zat ik netjes op 2 ms execution time maar toen ik mijn uiteindelijke input ging verwerken ging het even niet meer .

Niet om zout in wonden te strooien, maar ik quote even de eerste reactie uit het topic:

- peter - schreef op zondag 03 januari 2016 @ 21:36:
Wat hier altijd erg belangrijk bij is, is dat de voorbeeld input veel simpeler is dan de daadwerkelijke input. Wel wordt er aangegeven wat de limieten van de input variabelen kan zijn. Het is dan ook slim om daar mee te testen, en niet alleen met de voorbeeld input een brute force methode te verzinnen, die er bij de echte data uren over doet.

[dcm360]

Handige tip: maak zelf een generator die testcases maakt die wat grootte betreft op (of net over) de gegeven contraints zitten. Nu moet ik wel toegeven dat dat bij de laatste opgave nogal stressen was, aangezien mijn oplossing veel te traag leek, maar uiteindelijk heb ik die in de helft van de tijd in weten te leveren.

Momenteel heb ik drie van de opgaven ingeleverd, voor de derde opgave heb ik vooralsnog geen werkend algoritme (daar ga ik nu nog even aan schetsen).

edit: de derde is het niet geworden. Stackoverflow...

[ Voor 5% gewijzigd door dcm360 op 11-01-2016 22:40 ]

[Soultaker]

Nog een uur te gaan! Ik heb mijn oplossingen alvast in een blogpost gestopt:

• Facebook Hacker Cup 2016: Qualification Round problem analysis

Als het goed is, is die nu nog niet zichtbaar, maar over een uur wel.

[vliegnerd]

Mooie oplossingen, Soultaker!

Ik heb voor probleem 1 ongeveer hetzelfde O(n^2) algoritme, maar jouw code is mooier :-). Als ik de code van de nummer 1 van het leaderboard bekijk dan zie ik het "naieve" O(n^3) algoritme in C++. Best frustrerend, aangezien mijn Python O(n^2) algoritme ongeveer 4 minuten nodig had op mijn oude laptop.

Maar mijn greedy oplossing voor 2 (high security) lijkt analoog aan jouw O(n) oplossing, maar ik heb een kruisje. (Wrong Answer, neem ik aan). Zucht! Terwijl ik juist de moeite heb genomen om zelf een pak testcases te maken en te checken...

Uit probleem 3 ben ik niet gekomen. Ik ga jouw oplossing bestuderen.

Probleem 4 niet aan begonnen.

[ Voor 18% gewijzigd door vliegnerd op 12-01-2016 08:45 ]

[Qzar]

Bedankt voor je blog post Soultaker!
Erg leuk om te lezen, vooral de motivatie waarom je een bepaalde manier gebruikt en welke tussenstappen je hebt gemaakt.

[Soultaker]

vliegnerd schreef op dinsdag 12 januari 2016 @ 08:39:
Als ik de code van de nummer 1 van het leaderboard bekijk dan zie ik het "naieve" O(n^3) algoritme in C++. Best frustrerend, aangezien mijn Python O(n^2) algoritme ongeveer 4 minuten nodig had op mijn oude laptop.

Ja, dat vond ik ook een beetje flauw. Eigenlijk is zo'n probleem niet echt geschikt voor dit soort wedstrijd, waarbij verschillende deelnemers verschillende programmeertalen gebruiken en ook verschillende hardware tot hun beschikking hebben. Dan moet je eigenlijk zorgen dat het gat tussen de "slimme" en de "domme" oplossing zo groot is dat het ofwel voor iedereen werkt, ofwel voor niemand.

Maar mijn greedy oplossing voor 2 (high security) lijkt analoog aan jouw O(n) oplossing, maar ik heb een kruisje. (Wrong Answer, neem ik aan). Zucht! Terwijl ik juist de moeite heb genomen om zelf een pak testcases te maken en te checken...

Als je een hint wil, moet je je code maar posten.

Qzar schreef op dinsdag 12 januari 2016 @ 12:05:
Erg leuk om te lezen, vooral de motivatie waarom je een bepaalde manier gebruikt en welke tussenstappen je hebt gemaakt.

Bedankt!

[vliegnerd]

Ik heb minstens 1 denkfout in mijn "high security" implementatie gevonden:

Ik loop de rij van links naar rechts door en plaats telkens guards. Maar als er een enkele lege cel (X.X) in de andere rij langskomt dan verplaats ik de guard daarna toe, mits dat kan (niet al eerder verplaatst). Dat is dus een hele ingewikkelde manier om "plaats bij elke X.X een guard" te doen...

Doh!

De echte fout nog niet gevonden, maar dat is minder belangrijk: Mijn algo is al niet handig.

[Camulos]

@Soultaker: erg tof om weer je uitwerkingen te zien

De eerste had ik op exact dezelfde manier opgelost. Ook derde zat ik op hetzelfde pad, maar kreeg hem niet O(N).

Net als vliegnerd had ik een denkfout in mijn High Security zitten.

[Soultaker]

Zo, ik denk dat ik de problemen weer opgelost heb. Ik ga ze morgen nog wel even dubbelchecken voordat ik ze inlever. Wie is er nog meer mee bezig?

edit:
Er zitten trouwens wel weer een aantal problemen bij die met een scripttaal nauwelijks te doen zijn...

[ Voor 28% gewijzigd door Soultaker op 16-01-2016 22:26 ]

[Ghehe]

Soultaker schreef op zaterdag 16 januari 2016 @ 22:25:
Wie is er nog meer mee bezig?

Ik ben er nu naar aan het kijken. Vandaag mijn strategie/algo bepalen en morgen programmeren.

[Soultaker]

Urgh, die prutsers bij Facebook blijven de bounds op de testdata maar aanpassen. Pas goed op bij het tweede probleem!

[vliegnerd]

Helaas dit weekend geen tijd. Voor mij is de wedstrijd dus over (Ik doe toch alleen maar voor de lol mee, dus eigenlijk maakt het niks uit.).

Ik ga de problemen nog wel proberen deze week. Hopelijk kan ik me inhouden en niet naar de oplossingen van Soultaker kijken. Ik weet niet of je van plan bent die te publiceren, maar zo ja: Het wordt ERG op prijs gesteld.

[Ghehe]

vliegnerd schreef op zondag 17 januari 2016 @ 15:19:
Het wordt ERG op prijs gesteld.

QFT. Altijd leuk om Soultakers writeup te lezen.

[Soultaker]

Bij dezen: Facebook Hacker Cup 2016: Round 1 problem analysis

Het zal me benieuwen of er weer 500+ deelnemers 100 punten hebben gescored, net zoals vorig jaar. edit: Blijkbaar niet!

[ Voor 5% gewijzigd door Soultaker op 17-01-2016 19:28 ]

[Elijan9]

Soultaker schreef op zondag 17 januari 2016 @ 19:15:
...
Het zal me benieuwen of er weer 500+ deelnemers 100 punten hebben gescored, net zoals vorig jaar. edit: Blijkbaar niet!

Dit keer gaat iedereen met "minimaal 30 punten" door naar ronde 2... En dat met opdrachten van 15, 20, 25 en 40 punten Ik mag nog één keer doen alsof ik erbij hoor

[Soultaker]

Huh, dat hebben ze ook recent aangepast. Valt ook wel wat voor te zeggen: je moest wel haast perfect scoren om door te gaan deze ronde.

Voor mij wel ongunstig; nu is er veel meer concurrentie de volgende ronde!

[patrick.k]

Vanavond tijd voor de volgende ronde. Wat doen jullie daar nog voor aan voorbereiding vooraf om alles sneller te laten verlopen?

Ik kon zelf nog niet meer bedenken dan stukken code met templates voor input/output klaar te zetten.

[Soultaker]

Ik heb ook wat template/library code van eerdere wedstrijden, en een Makefile zodat ik minimaal tijd kwijt ben aan het compileren. Verder vind ik het fijn om pen en papier in de buurt te hebben, maar dat is het wel zo'n beetje. Ik zou niet weten wat ik verder nog zou kunnen voorbereiden...

[Soultaker]

We gaan van start Veel succes allemaal!

Ik vind wel dat de nieuwe regel van "iedereen met meer dan 30 punten gaat door naar Ronde 2" een slechte progressie oplevert. Hierdoor zijn 2293 van de 3633 deelnemers door (63%), terwijl in deze ronde slechts 200 deelnemers doorkunnen (9%). Ze hadden beter de lat een beetje hoger kunnen leggen, zodat elke ronde ongeveer hetzelfde percentage deelnemers doorgaat.

[patrick.k]

Succes nog.

Dat is inderdaad wel een beetje vreemd. Ik ga bij de 91% horen. Het wil niet lukken vandaag. Alleen de eerste klopt denk ik bij mij.

[Soultaker]

Crap. M'n oplossing voor het laatse probleem was te traag. Momenteel sta ik 550e; als de rest goed is krijg ik misschien nog een T-shirt

Ik heb zoooveel tijd verspild bij het uitzoeken van een efficiënte manier om die kwadraten uit te rekenen bij Snakes and Ladders. Dat wilde maar niet lukken.

edit:
Argh, nee he! Ik heb ergens:

C++:

return res;

... staan, waar het:

C++:

return m = res;

... had moeten zijn.

Nu draait 'ie in 4 seconden. Yep, nu is 'ie correct (vergeleken met de output van Eryx, die momenteel #1 staat). Ik heb op 2 karakters na de boot gemist.

[ Voor 75% gewijzigd door Soultaker op 23-01-2016 22:40 ]

[patrick.k]

Vervelend, maar er hebben vast genoeg mensen boven je fouten gemaakt.

Ik kreeg bij de tweede niet de goede antwoorden eruit voor alle voorbeelden. Voor de derde kon ik nog geen oplossing bedenken die snel genoeg was. De laatste heb ik niet eens meer geprobeerd.

Voor een volgende keer toch maar wat meer oefenen.

[Soultaker]

Write-up van ronde 2: Facebook Hacker Cup 2016: Round 2 problem analysis

Toch wel leuke problemen. Ik baal wel enorm dat ik het laatste probleem fout had. Nou ja, in ieder geval was m'n aanpak correct. Volgend jaar beter

[Eärendil]

Morgen start de Facebook Hacker Cup 2018. Dit keer niet in januari, maar in de zomer. Wel een beetje onhandig i.v.m. vakanties.

Ronde	Start	Duur	Eind
Online Qualification Round	zaterdag 7 juli 01:00	72 uur	dinsdag 10 juli 01:00
Online Round 1	zaterdag 21 juli 19:00	24 uur	zondag 22 juli 19:00
Online Round 2	zaterdag 4 augustus 19:00	3 uur	zaterdag 4 augustus 22:00
Online Round 3	zaterdag 18 augustus 19:00	3 uur	zaterdag 18 augustus 22:00
Onsite Finals at Facebook	25 - 27 oktober 2018

(Tijden zijn in CEST)

[Groax]

Wat is de programmeer taal die je mag/moet gebruiken?

[Soultaker]

Eärendil schreef op vrijdag 6 juli 2018 @ 10:29:
Morgen start de Facebook Hacker Cup 2018.

Is misschien een apart topic waard? (Je kunt een modje vragen de nieuwe berichten af te splitsen naar een nieuw topic.)

moese schreef op vrijdag 6 juli 2018 @ 15:56:
Wat is de programmeer taal die je mag/moet gebruiken?

Je mag elke programmeertaal gebruiken die je wilt. De manier waarop de wedstrijd werkt, is dat je de testinvoer downloadt, lokaal je programma uitvoert om antwoorden te berekenen, en vervolgens je uitvoer samen met de broncode uploadt.

Voor zover ik hier kan zien is de enige eis dat je broncode niet geöbfusceerd is: https://www.facebook.com/hackercup/terms/ (Ik heb trouwens geen idee hoe je deze pagina hoort te vinden; ik zag dat 'ie gelinkt werd vanaf de pagina van vorig jaar en blijkbaar zijn de Terms & Conditions geüpdatet voor 2018.)

[thechib12]

Wil het dit jaar ook wel eens proberen. Iemand een linkje naar de oude opdrachten, de links in de OP doen het niet

[Soultaker]

Kwalificatieronde vorig jaar: https://www.facebook.com/hackercup/problem/1254819954559001/
Kwalificatieronde dit jaar: https://www.facebook.com/hackercup/contest

edit:
En de kwalificatieronde is voorbij. Niet heel veel programmeerwerk tot nu toe, vooral veel wiskunde/puzzelen.

Voor de geïnteresseerden, hier zijn mijn oplossingen (in Python): https://gist.github.com/m...cb2f5f3903b5ceb0a9bfd4591.

[ Voor 44% gewijzigd door Soultaker op 10-07-2018 01:31 ]