Facebook Hacker Cup 2013

[CodeCaster]

Je hebt voor N kaarten een aantal mogelijke handen met K kaarten, gevraagd wordt de som van de scores van iedere mogelijke hand, waarbij de socre wordt bepaald door de hoogste kaart in die hand.

[Soultaker]

Drak0z schreef op zondag 03 februari 2013 @ 00:46:
[..] Ik breek alleen m'n kop over wat ze nou in 's hemelsnaam willen bij die CardGame... Ik heb net m'n eerste biertje gepakt, misschien helpt dat met nadenken ;-)

Ballmer peak

Re: Card Game: je moet je vooral niet blindstaren op die modulo-operatie. Die staat er alleen maar bij zodat je het probleem ook gewoon met 32-bits integers op kan lossen.

[ Voor 38% gewijzigd door Soultaker op 03-02-2013 00:57 ]

[Drak0z]

@Soultaker - Bonuspoints voor het snappen van de referentie ;-)
@CodeCaster - Volgens mij snap ik hem nu... Ik zal het zo even uitwerken, maar ik kwam er vooral niet uit dankzij het voorbeeld :-)

[Eärendil]

Ik heb net de laatste ingeleverd. Ik sta nu 589, dus als ik alles goed heb en genoeg anderen hebben fouten gemaakt…
Nadeel is dat ik natuurlijk ook nog weer kan zakken als iemand die sneller was met de eerste opdrachten ook nog de laatste inlevert.

[frG]

Heb ik eindelijk de card game opdracht klaar, red mijn oplossing het niet binnen de 6 minuten, was te verwachten natuurlijk.. ben erg benieuwd als de ronde voorbij is naar alle oplossingen hier

[MrHaas]

Helaas een foutje ontdek in 3, dus die heb ik sowieso fout. Balen...:(

[Drak0z]

CardGame was erg simpel toen ik hem eenmal doorhad... Echter had ik een hele domme fout gemaakt in mijn code die ik ontdekte na het opvragen van de opgaven. Ik kon deze (net) op tijd kon repareren en submitten... Alleen toen klapte mijn internet er voor een paar minuten uit (modem/router vond dat ie een update moest doen). Dat was een beetje jammer. De Ballmer peak kon hier ook niks aan doen

Security vond ik verdacht makkelijk, daar zal ik wel iets fout gedaan hebben

DeadPixels breek ik nog steeds mijn brein over de optimale oplossing. De brute force is erg simpel maar gaat uiteraard ruim over de 6 minuten heen wanneer extreme waarden gebruikt worden. Ik weet dat ik nooit van z'n langzalzeleven in de top500 zal belanden (mede doordat ik dus een foutieve CardGame gesubmit heb), maar ik wil 'm gewoon klaar hebben voor mezelf :-) Ik blijf hier nog lekker aan doorpuzzelen (tot ik met m'n hoofd op het toetsenbord in slaap val)

[Soultaker]

Ik heb uiteindelijk zowel Card Game als Dead Pixels redelijk brute force geïmplementeerd. Ik vond Security conceptueel juist het moeilijkste (en heeft me ook het meeste codewerk gekost) maar misschien heb ik gewoon iets simpels gemist — tenslotte is 'ie ook maar 35 punten waard.

[Drak0z]

*vloek en tier* Waarom kom ik er nou niet uit met die dooie pixels? Ik ben er zo dicht bij! En het is een (bijna) optimale oplossing... Ik kom alleen nog altijd dat laatste stapje te kort. Nog twee uurtjes en dan weet ik wat ik fout doe. Tot die tijd probeer ik in slaap te vallen (of het toch te fixen... Afhankelijk van hoe helder ik blijf als ik in bed lig )

[xos]

Zijn de opgaves ook al in te zien door iemand die niet meedoet? Was op vakantie tijdens de kwalificatie ronde en vind dit soort opdrachten leuk om met een taal te prutsen die ik niet ken. Kan de opdrachten van de qualificatieronde wel vinden maar nog niet voor ronde 1.

PS: Soultaker, leuke blogposts. Lees het met veel plezier.

[Drak0z]

xos - Dit is de huidige ronde van de Cup. Ik schat niet dat het nu werkt, maar misschien vanaf 19:00
https://www.facebook.com/...php?round=189890111155691

Net toch mijn (zeer) suboptimale oplossing voor de dooie pixels geprobeert te genereren. "java.lang.OutOfMemoryError: Java heap space" error... Oeps! Dat was zeker zeer sub-optimaal :-) Nouja, 10 minuten tot de uitslag en volgend jaar beter. Hopen dat ik dan niet zo veel koorts en hoofdpijn heb.

[ Voor 46% gewijzigd door Drak0z op 03-02-2013 18:51 ]

[Soultaker]

Zo, ik heb alvast mijn oplossingen online gezet. Ik zal er later vanavond nog een paar voorbeeldjes in editen; ik weet niet of de tekstuele beschrijving heel goed te volgen is.

@Drak0z: jammer, maar je hebt tenminste geprobeert. Respect voor het doorwerken tot de deadline

[ Voor 9% gewijzigd door Soultaker op 03-02-2013 19:18 ]

[Drak0z]

@Soultaker: Mooi om te zien dat je qua kaartenprobleem (bijna?) dezelfde ideeen had als ik.
Mijn oplossing voor Card Game (in pseudo-java):

spoiler:

TreeList (= sorted list) vullen met kaarten
MaxHanden berekenen door fac(n)/(fac(n-k)*(fac(k)))
k--;
zolang het aantal handen > 0 is en ik nog kaarten heb:
pak de laatste kaart (sorted list dus altijd hoogste waarde)
n--;
result += kaartwaarde*min(MaxHanden, fac(n)/(fac(n-k)*(fac(k))));
MaxHanden -= fac(n)/(fac(n-k)*(fac(k)));

Ik kwam hier alleen in de problemen omdat de faculteiten over de MaxValue van long heen gingen (nooit aan gedacht.... eenmaal opgelost (door gebruik te maken van BigDecimals) was het een combinatie van tijd op en internet stuk

De andere twee zal ik later uitwerken... Nu eerst slapen!

[MrHaas]

Mijn oplossingen in Python: https://gist.github.com/63b92ee871fe975446d1

[Soultaker]

MrHaas schreef op zondag 03 februari 2013 @ 19:34:
Mijn oplossingen in Python: https://gist.github.com/63b92ee871fe975446d1

Nette code, maar ik volg niet helemaal wat je bij Security precies probeert te doen, en volgens mij klopt 't ook niet helemaal, want ik krijg er net wat andere uitvoer uit. Bijvoorbeeld voor deze testcase:

27
?dd???ea???a?aadfade??d??fe?a??ecd????af??ccaaac??adb?
?ab?ad??a???e?be????db????d?f?db??de?c???dcd?f??c?b??a

Mijn antwoord:

addaaaeaaaaaaaadfadeaadaafeaaaaecdbabaafdbccaaacdbadbe

Jouw antwoord:

addaaaeaaaaaaaadfadeaadabfeaaabecddadbafdbccaaacfaadbe

De 25e letter is bij mij een 'a' en bij jouw een 'b'.

[Eärendil]

Ik heb 1 en 3 denk ik goed, en 2 fout. Ik kreeg veel te vaak 'IMPOSSIBLE' op de uiteindelijke input, en dacht al dat ik hier fout zat, maar had geen tijd om mijn fout te zoeken in 6 minuten.

Mijn Card Game oplossing gebruikt dezelfde combinatoriek als Soultaker, maar ik bereken de nCr waarden niet vooraf, maar elke keer opnieuw in de loop, met gmpy.comb in Python. Dit is in dit geval snel genoeg (5sec voor de 20 cases)

Mijn oplossing voor de dead_pixels was ongeveer dit:

• Reken de posities van de dead pixels uit en sla ze op in een map van kolomnr -> set van rijnummers
• Initialiseer een kolom-vector met elke rij = 0
• Voor alle kolommen:
  • als het rijnummer niet in de set van rijnummers van deze kolom zit => rij-waarde++
  • als het rijnummer wel in de set van rijnummers van deze kolom zit => rij-waarde = 0
  • maximum rij-waarde is de breedte van het te plaatsen blokje
  • elke range met waarde van minimaal breedte van het te plaatsen blokje en lengte van de range van minimaal hoogte van het te plaatsen blokje => verhoog uiteindelijke resultaat met aantal keer dat de hoogte in die range past

Als voorbeeld een scherm van 6x5, dode pixel in het midden en een te plaatsen blok van 3x2:

000000      123456      123333
000000      123456      123333
001000  =>  120123  =>  120123
000000      123456      123333
000000      123456      123333

Omdat het aantal dead pixels relatief laag is vergeleken met het totaal aantal pixels, kan dit sparse worden opgeslagen (elke rij is een kolom uit de bovenstaande tabel):

[(0,4,1)]
[(0,4,2)]
[(0,1,3), (2,2,0), (3,4,3)]
[(0,1,3), (2,2,1), (3,4,3)]
[(0,1,3), (2,2,2), (3,4,3)]
[(0,1,3), (2,2,3), (3,4,3)] = [(0,4,3)]

Dat scheelt in aantal berekeningen en maakt het berekenen van de lengte van de range ook een stuk makkelijker. Wel moet er na elke kolom gemerged worden (zie laatste regel)

[Soultaker]

Het zal mij benieuwen hoeveel deelnemers uiteindelijk alles goed hebben; nu zijn het er 926, maar ik denk dat er heel wat zullen falen, bijvoorbeeld op probleem 2. Het is heel makkelijk om daarin een subtiele fout te maken die door de (vrij karige) sample cases niet afgevangen wordt. Verder zullen de nodige mensen nog last hebben van integer overflows in probleem 1.

Ik wed sowieso dat de huidige nummer 1 faalt, en dat Eryk (nu tweede) deze ronde gaat winnen, want van Eryk weet ik dat 'ie heel goed was (hij haalde in 2011 ook de finale), en zijn tijd is enorm scherp (ter vergelijking: als je elk probleem in exact 10 minuten oplost, heb je een cumulative straftijd van 60 minuten, en dan sta je nóg onder 'm ).

[MrHaas]

Soultaker schreef op zondag 03 februari 2013 @ 21:15:
[...]

Nette code, maar ik volg niet helemaal wat je bij Security precies probeert te doen, en volgens mij klopt 't ook niet helemaal, want ik krijg er net wat andere uitvoer uit. Bijvoorbeeld voor deze testcase:

27
?dd???ea???a?aadfade??d??fe?a??ecd????af??ccaaac??adb?
?ab?ad??a???e?be????db????d?f?db??de?c???dcd?f??c?b??a

Mijn antwoord:

addaaaeaaaaaaaadfadeaadaafeaaaaecdbabaafdbccaaacdbadbe

Jouw antwoord:

addaaaeaaaaaaaadfadeaadabfeaaabecddadbafdbccaaacfaadbe

De 25e letter is bij mij een 'a' en bij jouw een 'b'.

Ja, zag t ook, waarschijnlijk pak ik niet de optimale sequence qua alfabetische volgorde.

[Drak0z]

Zoals verwacht was mijn oplossing voor Security fout. Ik moet nog uitzoeken wat ik fout deed, maar dat komt na m'n werk.

Mijn idee bij de Dead Pixels (waar ik uiteindelijk op vast kwam te zitten); letterlijke copy/paste uit mijn code

Java: deadpixels.java

numPossibilities = (w-p+1)*(h-q+1);

while (deadPixels.size() > 0) {
  Pixel pixel = deadPixels.pollFirst();
  int invalidPos = invalidPositions(pixel, w, h);
  if (deadPixels.size() > 0) { // chance for overlap
    // "revalidate" double invalidated positions --- where the square overlaps multiple dead pixels
    // I know there is a mathematically correct way to do this, my brain's just failing :-)
    // TODO: check the pixels again, check how many are in range of the current pixel ... ? profit!
  }
  numPossibilities -= invalidPos;
}
return numPossibilities;

int invalidPositions(Pixel pixel, int w, int h) {
  if (x-(p-1) < 0) { multiX += x-(p-1); } // overlaps left
  if (y-(q-1) < 0) { multiY += y-(q-1); } // overlaps top
  if (x+p > w) { multiX -= ((x+p)-w); } // overlaps right
  if (y+q > h) { multiY -= ((y+q)-h); } // overlaps bottom
  return multiX*multiY;
}

De oplossing die ik uiteindelijk gewoon ging proberen was alle 'top left' coordinaten van een invalid square opslaan in een hashset (zodat ze altijd uniek zijn) en dat aftrekken van numPos.... Maar dat ging dus over z'n memorylimit heen :-)

[Eärendil]

Ik had problem 2 zoals verwacht fout en val daarmee dus buiten de 500.
Heeft er behalve Soultaker nog iemand anders de volgende ronde gehaald?

[Soultaker]

Dat die vraag onbeantwoord blijft voorspelt niet veel goeds...

Woy schreef op zaterdag 02 februari 2013 @ 20:48:
Helaas geen tijd nu, ik kijk morgen ochtend nog wel even, maar dan heb ik natuurlijk al geen enkele kans meer om door te gaan naar de volgende ronde.

Dat bleek achteraf dus best mee te vallen!

[MrHaas]

Soultaker schreef op maandag 04 februari 2013 @ 22:34:
Dat die vraag onbeantwoord blijft voorspelt niet veel goeds...


[...]

Dat bleek achteraf dus best mee te vallen!

Ja, inderdaad, had ik maar iets meer tijd genomen om problem 3 nog x te testen...

Heb problem 2 trouwens gefixt in de Gist, jammer dat ik ook die niet direct goed heb getest.

Succes btw in de volgende ronde!

[ Voor 4% gewijzigd door MrHaas op 05-02-2013 13:52 ]

[- peter -]

Wow Soultaker, je blog is gelinked in de uitleg van Facebook van ronde 1!

[Woy]

Soultaker schreef op maandag 04 februari 2013 @ 22:34:
Dat bleek achteraf dus best mee te vallen!

Nou heb ik 's ochtends ook niet echt gered

[Soultaker]

Ronde 2 begint over twintig minuten, maar ik zie nog geen linkje... hoop dat ze 't niet vergeten zijn.

Wel irritant dat 't nu zo laat is (van 10 uur 's avonds tot 1 uur 's nachts); ik hoop dat ik een beetje helder kan denken. Ik vond het vorige week juist fijn dat ik rond een uur of tien klaar was.

[Ghehe]

Deze link staat in mijn newsfeed: https://www.facebook.com/...php?round=499927843385312

In ieder geval: Veel geluk.

[Soultaker]

Ah, nu zie ik 'm ook. Bedankt!

Eens zien of ik een T-shirt kan scoren vanavond.

edit:
Blegh, m'n oplossing voor probleem 3 werkt niet. Balen. Ik vermoed dat ik nu rond de 250e plek uitkom.

[ Voor 59% gewijzigd door Soultaker op 10-02-2013 01:08 ]

[MrHaas]

En, wat is het geworden?

Ik ga morgen es kijken hoe ver ik kom...

[Soultaker]

Ik had uiteindelijk alleen het tweede probleem goed, en eindigde op de 236e plek. Toch nog in de bovenste helft Het zijn wel leuke probleem op zich. Jullie kunnen ze nu ook zien neem ik aan?

[iChaos]

Ik zie dit topic nu pas en vroeg me af: zijn er websites waar men gewoon als oefening dergelijke opdrachten voorlegt zodat programmeurs ook kunnen puzzelen? Een soort digitaal puzzelboek waarbij je steeds leunt op algoritmen/bruteforcen/programmeren etc. Dit ziet er wel uit als een leuke manier om mijn tijd te besteden wanneer ik een keer niks te doen heb.

[Soultaker]

• Project Euler is vrij bekend (maar leunt erg sterk op wiskunde, wat niet iedereen leuk vindt).

• USACO Training Program is meer traditioneel van opzet, en bouwt goed op qua moeilijkheid, hoewel niet alle testdata even goed is (maar daar heb je vooral later last van).

Als je live wedstrijden leuk vind, kun je mee doen met TopCoder of CodeForces (die laatste is wat moeilijker, mede doordat het door Russen geschreven Engels soms lastig te decoderen is). Wel een aanrader als je wil oefenen voor de Facebook Hacker Cup of de Google Code Jam (die volgende maand gehouden wordt, geloof ik?)

Verder worden/werden er op dit subforum nog wel eens programmeerwedstrijden gehouden, georganiseerd door de crew of door users. Ik geloof dat de crew een nieuwe contest gepland had voor in de zomer van 2010 ofzo, maar dat is er nooit van gekomen helaas.

[kokx]

Ik heb nog een paar andere resources hiervoor. Hoewel deze meer gericht zijn op de ICPC (programmeer wedstrijden gesponsord door IBM).

UVa Online Judge
Veel oude opgaven van ICPC wedstrijden. Insturen in Java, C++ of C en de server runt en valideert jouw programma automatisch.. Al raad ik Java niet aan, dat werkt helaas niet zo goed.
SPOJ Zelfde opzet als UVa.

En de USACO training tool is altijd goed om wat in te doen. Er zitten erg geavanceerde onderwerpen tussen die goed uitgelegd worden.

[MrHaas]

Op de site van Google Code Jam kan je de opgaven van voorgaande jaren bekijken en laten checken.

Als je Python leuk vindt (alhoewel je ook andere taal kan gebruiken voor meeste challenges), kijk dan ook eens naar Python Challenge. Wat minder algoritmisch van aard, maar wel leuk om mee bezig te zijn.

[Eärendil]

De Hacker Cup 2014 begint al volgend weekend, dus twee maanden eerder dan vorige jaren:

Ronde	Start	Duur	Eind
Online Qualification Round	vrijdag 22 november 01:00	72 uur	maandag 25 november 01:00
Online Elimination Round 1	zaterdag 7 december 19:00	24 uur	zondag 8 december 19:00
Online Elimination Round 2	zaterdag 14 december 19:00	3 uur	zaterdag 14 december 22:00
Online Elimination Round 3	zaterdag 21 december 19:00	3 uur	zaterdag 21 december 22:00
Onsite Finals at Facebook	20 en 21 februari 2014

https://www.facebook.com/hackercup

[ Voor 81% gewijzigd door Eärendil op 18-11-2013 01:39 ]

[Verwijderd]

Leuk! Vorig jaar miste ik helaas, dit jaar wil ik echt graag meedoen!

[Eärendil]

Ik heb voor de editie 2014 een nieuw topic aangemaakt: Facebook Hacker Cup 2014