Facebook Hacker Cup 2017

[HuHu]

Facebook Hacker Cup 2017

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 2017?

Ronde	Start	Duur	Eind
Online Qualification Round	zaterdag 7 januari 01:00	72 uur	dinsdag 10 januari 01:00
Online Elimination Round 1	zaterdag 14 januari 19:00	24 uur	zondag 17 januari 19:00
Online Elimination Round 2	zaterdag 21 januari 19:00	3 uur	zaterdag 23 januari 22:00
Online Elimination Round 3	zaterdag 28 januari 19:00	3 uur	zaterdag 30 januari 22:00
Onsite Finals at Facebook	nog niet bekend

(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
2016	Final	Snake and Ladder Boomerang Crews Grundy Graph RNG Maximinimax Flow	Solutions
	3	Link	Solutions
	2		Solutions
	1	Link	Solutions
	Qual	Link	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
Facebook Hacker Cup 2016

[ Voor 210% gewijzigd door HuHu op 07-01-2017 11:19 ]

[Soultaker]

Linkje naar kwalificatieronde. (Je kunt nog mee doen tot maandagavond. Wel eerst registreren).

Ligt het aan mij of is het eerste probleem ("Progress Pie") nogal ondergespecificeerd? Hoe bepaal je of een pixel op de rand van de taartpunt wit of zwart is? Dit zou het eenvoudigste probleem moeten zijn, maar het is de enige waarvan ik niet zeker ben dat ik 'm op kan lossen.

[Verwijderd]

Soultaker schreef op zondag 8 januari 2017 @ 14:55:
Linkje naar kwalificatieronde. (Je kunt nog mee doen tot maandagavond. Wel eerst registreren).

Ligt het aan mij of is het eerste probleem ("Progress Pie") nogal ondergespecificeerd? Hoe bepaal je of een pixel op de rand van de taartpunt wit of zwart is? Dit zou het eenvoudigste probleem moeten zijn, maar het is de enige waarvan ik niet zeker ben dat ik 'm op kan lossen.

Bij de constraints staat nog vermeld dat voor elk query punt zijn omgeving binnen een straal van 10^-6 ook dezelfde kleur heeft. Punten op de rand voldoen hier natuurlijk niet aan .

[Soultaker]

Dat zag ik, maar dat maakt de verwarring alleen maar groter, want alle pixels hebben integer coördinaten. Wat moet ik me dan precies voorstellen bij een straal van 10^-6 om een pixel heen?

Concreet voorbeeld: de afstand van (50,100) tot het midden op (50,50) is precies 50. Die pixel is dus zwart (als P>0). Maar (51,100) heeft een afstand groter dan 50, dus die is sowieso wit. Maar in het voorbeeldplaatje is die toch zwart. Het lijkt er dus op dat een soort midpoint circle algoritme gehanteerd wordt waarbij een pixel zwart is als enig deel van de pixel doorsneden wordt.

Je zou ook anders kunnen redeneren: een pixel is zwart as minstens 50% van de inhoud zwart is (dan is weer de vraag: wat als exact 50% zwart is...) maar dat lijkt niet het geval te zijn.

En dan is de vraag of dezelfde logica wordt toegepast op de rechte lijn die de cirkelboog met het midden verbind. Het lijkt er wel op, maar het is me uit het plaatje niet helemaal duidelijk.

Misschien doet het er niet toe omdat in de testdata nooit om de kleur van een problematische pixel gevraagd wordt, maar ook dat is van te voren niet echt duidelijk, waardoor het riskant is om er blind vanuit te gaan.

[HuHu]

Het is inderdaad een onduidelijke vraag. Ik vind het ook vaag waar (50, 50) nu precies ligt. Is dat het midden van de middelste pixel of de linker-onder hoek van de middelste pixel? Indien het eerste (dat vermoed ik), dan ligt het centrum van de cirkel dus op (50.5, 50.5).

De afstand van (50.5, 50.5) naar (51, 100) is dan <50 en dus zwart.

[Soultaker]

Als pixel (50,50) coördinaten (50.5, 50.5) heeft (midden van de pixel), dan heeft pixel (51, 100) natuurlijk coordinaten (51.5, 100.5) en dan is de afstand dus weer > 50.

Zoals op dit plaatje: https://upload.wikimedia....2/24/Bresenham_circle.svg

De eerste vier pixels op de eerste rij zijn alleen gekleurd omdat ze de cirkel gedeeltelijk doorsnijden. Maar de afstand tot het midden is duidelijk groter dan de straal. (Je kunt dat in dat plaatje goed zien omdat de cirkel ingetekend is.)

[HuHu]

Soultaker schreef op zondag 8 januari 2017 @ 16:14:
Als pixel (50,50) coördinaten (50.5, 50.5) heeft (midden van de pixel), dan heeft pixel (51, 100) natuurlijk coordinaten (51.5, 100.5) en dan is de afstand dus weer > 50.

Zoals op dit plaatje: https://upload.wikimedia....2/24/Bresenham_circle.svg

De eerste vier pixels op de eerste rij zijn alleen gekleurd omdat ze de cirkel gedeeltelijk doorsnijden. Maar de afstand tot het midden is duidelijk groter dan de straal. (Je kunt dat in dat plaatje goed zien omdat de cirkel ingetekend is.)

Nee, de correctie van 0.5 moet dan eenmaal worden toegepast: namelijk op het centrum van de cirkel. Mijn stelling is dat het centrum van de cirkel feitelijk op (50.5, 50.5) ligt. Het midden van de middelste pixel. (51,100) is de linker-onderhoek van die betreffende pixel. Daar hoef je dan niet nogmaals .5 bij op te tellen en verklaart dan ook waarom die pixel zwart is.

edit: ik bedenk me nu net dat dit niet op gaat voor alle pixels links van het centrum.

[ Voor 4% gewijzigd door HuHu op 08-01-2017 16:21 ]

[Soultaker]

Als dat zo is, dan is de bitmap niet symmetrisch. Alle punten met X=0 of Y=0 zijn dan wit, omdat de cirkel een halve pixel naar rechtsboven verschoven is.

Dat zou logisch zijn als de bitmap even afmetingen had, maar de invoer heeft het over 0 <= X,Y <= 100, wat suggereert dat de bitmap 101x101 pixels groot is; ik zou dan een symmetrische cirkel verwachten met pixel (50,50) als middenpunt.

Hoe weet je trouwens dat het centrum naar rechtsboven verschoven is en niet bijvoorbeeld naar linksboven?

[HuHu]

(0,0) zit linksonder en (100,100) rechtsboven, dus dan zou het naar rechtsboven verschuiven. Omdat een pixel ook nog een fysieke grootte heeft (pixel 0 loopt van 0.00 tot en met 0.99) zou de rechterrand van het plaatje dus op x=100.99 zitten.

Ik zou dus denken dat het centrum van de cirkel op 50.50 zit. Daarnaast zou de cirkel ook nog een radius van 50.5 (diameter van 101) kunnen hebben.

[Soultaker]

Zoiets was ook mijn interpretatie, maar een straal van 50.5 nemen en alleen de pixels kleuren waarvan het centrum op afstand <= 50.5 van het midden ligt, is niet hetzelfde als het midpoint circle algoritme toepassen met een straal van 50.

In ieder geval krijg ik verschillende antwoorden afhankelijk van hoe ik het precies implementeer, dus ik zal deze opgave wel "fout" hebben. Het maakt voor de kwalificatie-ronde niet echt uit (ik ga er vanuit dat ik de andere twee opgaven goed heb), maar ik blijf erbij dat de opgave ambigu is en dat het dus toevallig is of je implementatie overeenkomt met dat van de vraagsteller

Moraal van het verhaal voor andere deelnemers: als je er bij het eerste probleem niet uitkomt, geef dan niet op, maar probeer één van de andere twee problemen op te lossen. Die zijn beter geformuleerd.

[ Voor 14% gewijzigd door Soultaker op 08-01-2017 16:49 ]

[Verwijderd]

In de input zijn de punten inderdaad geheeltallig, maar ik lees nergens dat dat in zijn algemeenheid zo is. Maar ik ben het er wel mee eens dat het een stuk duidelijker uitgelegd had moeten worden. Het is extra vervelend omdat je in feite maar een poging hebt.

Het is mij gelukt om een oplossing te bedenken voor alle drie de opgaven. Mijn code voor de eerste opgave bevat zeker een bug, maar er is geen testcase die hem aan het licht brengt, dus ik hoop er toch nog de volle 25 punten voor te krijgen.

[vliegnerd]

Is de score die je krijgt fictief? (Ik heb 100 punten maar 3 vraagtekens, kan me voorstellen dat je pas achteraf de punten krijgt).

Ik heb ze alle drie opgelost Ik vond de derde wel leuk, want ik moest er echt over nadenken hoe de frequenties voor bijvoorbeeld een 20d20 worp "snel" te bepalen. Ben benieuwd of ik die goed heb.

Wat betreft de eerste opgave: Ik had mij niet met de afmetingen van pixels bezig gehouden. Interessant. Ben benieuwd of dat echt onderdeel van de opgave is, of gewoon een ondergespecifieerd probleem. Als het eerste waar is, dan is de opgave een heel stuk moeilijker dan ik dacht :-)

[Soultaker]

vliegnerd schreef op maandag 9 januari 2017 @ 21:02:
Is de score die je krijgt fictief? (Ik heb 100 punten maar 3 vraagtekens, kan me voorstellen dat je pas achteraf de punten krijgt).

Ja, is provisorisch. Als de ronde afgelopen is worden de vraagtekens vervangen door een vinkje of een kruisje en weet je wat je echte score is.

[HuHu]

De oplossingen: https://m.facebook.com/no...lutions/1593063774042851/

Voor de progress pie hebben ze de meeste simpele berekening aangehouden, die volgens mij niet klopt met het originele voorbeeld plaatje.

[vliegnerd]

De oplossing van 3 (Fighting the zombie) is interessant. Ik heb het geinterpreteerd als een simulatieprobleem en mijn energie gestoken in het snel bepalen van de kansen per uitkomst voor worpen zoals 20d20. Blijkbaar heb ik geluk dat er geen 1000 testcases met 1000d1000 worpen zijn. Mijn methode (python) werkt goed tot 100d100 ofzo, wat ruim voldoende is voor deze opgave.

Mijn oplossingen (python).

[vliegnerd]

Het zal wel aan mij liggen, maar in mijn facebookpagina 'Facebook hacker cup' staat *GEEN* link naar de Q1 ronde... Ik dacht al dat ik misschien toch niet toegelaten was, maar ik heb wel een mail ontvangen waarin staat dat ik door was.

Gisteravond dus wellicht wel tijd, geen opgaven... Vandaag geen tijd.

Inmiddels staat er in de comments wel een link:
https://www.facebook.com/...60474397/?hc_location=ufi

Nice, facebook.

[Soultaker]

(Even wat spoilers weggehaald.)

[ Voor 106% gewijzigd door Soultaker op 15-01-2017 14:54 ]

[vliegnerd]

@Soultaker: De ronde is voorbij, kom maar op met die spoilers ;-)

Ik heb de analyses op jouw blog altijd erg gewaardeerd!

[Soultaker]

vliegnerd schreef op maandag 16 januari 2017 @ 06:16:
@Soultaker: De ronde is voorbij, kom maar op met die spoilers ;-)

Ah, ik had mezelf vooral in de war gebracht bij het tweede probleem (met zombies op een 2D vlak, waarbij je een groep binnen een cirkel mag verplaatsen, en vervolgens binnen een vierkant met een gegeven zijde alle zombies kan vernietigen).

Ik zat te denken dat je simpelweg twee vierkanten kunt zoeken en het totale aantal zombies dat zich in de ene of het andere vierkant bevind (of beide) tegelijk kunt vernietigen. Dat was redelijk makkelijk te brute-forcen (weliswaar niet zo efficiënt, maar als het binnen een paar minuten kan, is dat goed genoeg).

De logica daarachter is dat je het tweede vierkant makkelijk over het eerste kunt verplaatsen. Maar toen begon ik aan mijn oplossing te twijfelen omdat op de een of andere manier in m'n hoofd had dat de cirkel die je verplaatst dan de kleinst mogelijk cirkel zou zijn die de te verplaatsen zombies bevat.

Bijvoorbeeld als de invoer zoiets is:

   1                10 11               20
 1 o . . . . . . . . o o . . . . . . . . o
   . . . . . . . . . . . . . . . . . . . .
   . . . . . . . . . . . . . . . . . . . .
   . . . . . . . . . . . . . . . . . . . .
   . . . . . . . . . . . . . . . . . . . .
 5 . . . . . . . . . o o . . . . . . . . .
   . . . . . . . . . . . . . . . . . . . .
   . . . . . . . . . . . . . . . . . . . .
   . . . . . . . . . . . . . . . . . . . .
10 o . . . . . . . . o o . . . . . . . . o

... en de zijde van je vierkant is precies 9, dan kun je bijvoorbeeld de linker vijf punten direct vernietigen (vierkant van (1,1) tot (10,10)), en de rechter vijf punten 10 naar links verplaatsen. Ik dacht echter dat dat niet kon, want als je een cirkel trekt door de vier hoekpunten aan de rechterkant (op (11,1), (20,1), (11,10), (20,10)) dan vang je daar niet alleen punt (11, 5) mee, maar ook (10, 5), en als je die 10 punten naar links verplaatst, duw je 'm juist weer buiten je vierkant. Dus op die manier kun je maximaal 9 zombies vernietigen, niet 10.

De truc is echter dat je cirkel willekeurig groot kan zijn, dus je kunt in dit geval een cirkel definiëren die bijvoorbeeld door punten (11, 1), (10.5, 5), (11, 10) gaat. En op die manier kun je dus wel elke rechthoek over de andere verplaatsen, want als de twee vierkanten elkaar niet raken, dan kun je altijd een (mogelijk heel grote) cirkel tekenen die de ene bevat en de andere niet overlapt. Het kan zijn dat die cirkel veel groter is dan het vierkant, maar dat maakt niet uit. Het duurde even voordat ik dat besefte.

(Het is ook mogelijk dat in de optimale oplossing de twee vierkanten deels overlappen, maar dan treedt het bovengenoemde probleem niet op, omdat je de punten minder ver verplaatst dan je vierkant groot is.)

Ik heb de analyses op jouw blog altijd erg gewaardeerd!

Dat is leuk om te horen! Ik had er dit jaar helaas geen tijd voor. Misschien dat ik zaterdagavond nog wat schrijf over de tweede ronde, mits ik de problemen weet op te lossen. De laatste tijd publiceert Facebook zelf ook vrij snel de oplossing van de problemen, dus misschien dat mijn blogposts minder nut hebben (al kan de analyze natuurlijk nog wel verschillen).

[vliegnerd]

Soultaker schreef op donderdag 19 januari 2017 @ 20:15:
[...]
De laatste tijd publiceert Facebook zelf ook vrij snel de oplossing van de problemen, dus misschien dat mijn blogposts minder nut hebben (al kan de analyze natuurlijk nog wel verschillen).

Het is inderdaad waar de de oplossingen van Facebook er snel zijn. Maar analyses zoals hierboven worden nog steeds gewaardeerd. Maar het is natuurlijk logisch dat je er wel tijd voor moet hebben en voor kunnen vrijmaken.

Veel succes in ronde 2 zaterdag!

[Soultaker]

Het was geen goede avond voor mij. Ik heb uiteindelijk alleen het eerste probleem op kunnen lossen.

Ik heb me lang blind zitten staren op het derde probleem waarvoor ik een goed idee dacht te hebben, maar ik kwam er uiteindelijk toch niet uit. Toen ben ik in het laatste halfuur teruggeschakeld naar het tweede probleem, waar ik wel een goed idee voor had, maar ik deed er net te lang over om m'n oplossing af te maken. (Ik heb 'm wel afgemaakt een kwartier buiten de tijd. Tenminste, ik denk dat 'ie goed is.)

Uiteindelijk heb ik dus geen van beide in kunnen sturen (wel natuurlijk het eerste probleem). Achteraf was het misschien beter geweest om te focussen op het tweede probleem, zodat ik die tenminste binnen redelijke tijd in had kunnen sturen, maar waarschijnlijk was dat nog niet goed genoeg geweest om in de top 200 te eindigen (wat nodig was om door te gaan naar de derde ronde). Helaas, volgend jaar beter.

Heeft iemand anders nog meer succes gehad?

[Verwijderd]

Ik had goede hoop om een t-shirt te winnen omdat ik een goede oplossing voor het tweede probleem dacht te hebben. De laatste testcase uit het voorbeeld was behoorlijk sterk, dus dat gaf me veel vertrouwen in de correctheid van mijn oplossing. Maar helaas kreeg ik toch een rood kruisje te zien bij de einduitslag .
Op de eerste opgave heb ik flink zitten prutsen en ik heb uiteindelijk ook daar een oplossing voor opgestuurd, maar die bleek ook niet te kloppen. Daar was ik al bang voor, omdat ik er niet overtuigd van was dat ik alle gevallen goed afhandelde.
Dus 0 punten voor mij. Hopelijk gaat het bij de google codejam beter. Gelukkig weet je daarbij wel meteen of je oplossing voor de small input correct is of niet.