Facebook Hacker Cup

[Tharulerz]

De Facebook hacker cup is weer begonnen (deze nacht om 1 uur), dit keer met iets minder tromgeroffel als vorige keer.

Zijn er nog tweakers die meedoen dit jaar? Soultaker is vorig jaar tot in silicon valley geraakt (laatste 25 dacht ik?), iemand zin hem op te volgen?

Info op https://www.facebook.com/hackercup .

Uit ervaring van vorig jaar: de eerste 2 rondes zijn redelijk doenbaar voor alle hobby en professionele programmeurs, daarna wordt het pittiger.

Tip: gebruik de lowest level taal die je kent. Als je java of c++ kent, is het vaak voordeliger om in c++ te werken, omdat je performance an sich al iets sneller zal zijn, en je daar dus minder tijd in moet steken. (Alhoewel een goed algoritme zoeken nog altijd veel belangrijker is dan de programmeertaal).

Veel succes!

[Soultaker]

Ha, goed dat je 't zegt, anders had ik het me niet eens gerealizeerd.

Ik ga wel weer een poging wagen. (Jij ook, neem ik aan?)

edit: de "website" is nog steeds behoorlijk verwarrend.

Tip: gebruik de lowest level taal die je kent. Als je java of c++ kent, is het vaak voordeliger om in c++ te werken, omdat je performance an sich al iets sneller zal zijn, en je daar dus minder tijd in moet steken.

Ik zou mensen aanraden om de taal te gebruiken waar ze het meest ervaren in zijn. Als je professioneel Java-programmeur bent en op z'n best een beetje C++ kan, dan ben je echt veel beter af met Java, vooral omdat beide talen performant genoeg zijn om alle problemen mee op te kunnen lossen (wat niet per se geldt voor bijvoorbeeld PHP of Ruby).

Als je onervaren bent is de kans groot dat je kleine foutjes maakt die je normaal gesproken wel zou kunnen fixen maar die in de context van een wedstrijd als deze je de kop kosten. Dat risico kun je beter niet nemen.

[ Voor 85% gewijzigd door Soultaker op 21-01-2012 10:53 ]

[Megamind]

Ik gebruik gewoon C#, lekker snel in prutsen en de eerste categorieën hebben toch weinig stampwerk nodig. Ben begonnen met de 3e opdracht aangezien die wel erg simpel was.

[pientertje]

Ik heb de eerste opdracht gedaan en ingeleverd. Ik snap alleen niet precies hoe de input en output werkt. Ik heb nu maar gedaan dat mijn programma het bestand 'billboards.txt' leest en het antwoord schrijft naar 'billboards_out.txt'. Klopt dit? Ik kon hier niet zo snel wat over vinden.

[Ghehe]

Heb me net ook ingeschreven. Heb dinsdag examen Algoritmen dus zo doe ik toch nog iets nuttig voor dat vak.

De derde opdracht is inderdaad wel heeeeel simpel. Ik was eerst met de eerste begonnen, die is toch ietsje moeilijker. (maar niet ondoenbaar)

[Soultaker]

pientertje schreef op zaterdag 21 januari 2012 @ 21:29:
Ik heb de eerste opdracht gedaan en ingeleverd. Ik snap alleen niet precies hoe de input en output werkt. Ik heb nu maar gedaan dat mijn programma het bestand 'billboards.txt' leest en het antwoord schrijft naar 'billboards_out.txt'. Klopt dit?

Dat is prima. Je mag helemaal zelf bepalen hoe je I/O doet, als je maar zorgt dat je na de officiële testinvoer gedownload te hebben, binnen 6 minuten de juiste uitvoer kan produceren (die je dan weer moet uploaden). Hoe je dat voor elkaar krijgt maakt allemaal niet uit.

Ghehe schreef op zaterdag 21 januari 2012 @ 21:30:
De derde opdracht is inderdaad wel heeeeel simpel. Ik was eerst met de eerste begonnen, die is toch ietsje moeilijker.

De derde en de eerste zijn allebei makkelijk inderdaad; de tweede is erg moeilijk. Ik heb 'm in ieder geval al verprutst.

[pientertje]

Nou nummer een en drie zijn af. Die tweede is wel de moeilijkste. Ik programmeer trouwens in python, snelheid is nu nog niet echt een issue.

Mogen we hier dingen discussiëren over die tweede? Bijvoorbeeld of mijn lijst met gewichten en prijzen klopt voor het eerste voorbeeld?

edit:
laat maar, ik heb de tweede ook verprutst. Ik had hier dus wel problemen met dat mijn programma niet snel genoeg was. De voorbeelden werkten prima, maar het werkelijke aantal producten was echt huge (groot als in: 7 * 10^15).

[ Voor 100% gewijzigd door pientertje op 21-01-2012 22:35 ]

[Megamind]

Ik ga nu aan de 2e beginnen. De 1e en 3e waren makkelijk op te lossen met creatieve loopjes, maar deze is toch behoorlijk pittig.

[ Voor 26% gewijzigd door Megamind op 22-01-2012 11:14 ]

[Tharulerz]

Ik heb voorlopig enkel de laatste gemaakt, aangezien 1tje genoeg is om door te gaan en je punten niet worden over gedragen naar de volgende ronde.

De vorige tijd steek ik voorlopig in examens leren

[Jegorex]

Ik kan er dit weekend niet aan werken, maar ik heb tot dinsdag 1 uur 's nachts de tijd?

[Ulster Seedling]

Goed dat ik dit topic zie, anders zou ik het helemaal vergeten zijn!

Ik heb net alle drie problemen opgelost. Helaas bleek mijn oplossing voor het tweede probleem (Auction) iets te inefficiënt te zijn: het PHP-scriptje bestaande uit een aantal loopjes had zelfs met 4GB RAM niet voldoende geheugen en kostte daarnaast veel te veel tijd. Misschien was het ook wel een beetje naïef om het zo aan te pakken, kijkend naar de input-waardes die je kon verwachten (1 ≤ N ≤ 10¹⁸)

Gelukkig zijn de andere twee problemen wel goed en op tijd ingeleverd, dus ik ben in ieder geval door naar de volgende ronde

[Megamind]

Kan iemand misschien zijn waardes voor P en W delen? Ik krijg namelijk voor P bij de eerste testcase "1,2,3,4,5". Dit lijkt me niet te kloppen aangezien dan het antwoord niet klopt.

[pientertje]

Met het eerste voorbeeld heb ik als prijzen: [1, 2, 3, 4, 5] en als gewichten [4, 7, 3, 6, 2]. Maar je moet de vraag echt goed lezen. Een product A is niet een koopje als het beter is dan een ander product B. A is een koopje als er geen B is die beter is dan A. Een groot verschil!

We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price).

We shall call a product A a bargain if there is no product B such that B is better than A.

[Megamind]

pientertje schreef op zondag 22 januari 2012 @ 11:09:
Met het eerste voorbeeld heb ik als prijzen: [1, 2, 3, 4, 5] en als gewichten [4, 7, 3, 6, 2]. Maar je moet de vraag echt goed lezen. Een product A is niet een koopje als het beter is dan een ander product B. A is een koopje als er geen B is die beter is dan A. Een groot verschil!


[...]

Dan klopt mijn iteratie wel. Maar ik veronderstelde dan dat 1 het koopje was en niet 3, even beter lezen dus

[pientertje]

En trap niet in de val waar ik en de mensen hierboven ingetrapt zijn. De inputs zijn HUGE, bereid je hierop voor!

[Soultaker]

Dat was gegeven de constraints wel te verwachten, natuurlijk. Ook in de volgende ronden kun je er vanuit gaan dat de testdata de moeilijkste gevallen bevat die (binnen de constraints van het probleem) mogelijk zijn.

[wackmaniac]

Nummertje drie ingeleverd. Redelijk weinig tijd vandaag, dus ik laat de rest voor wat het is.

[Megamind]

Nummer 2 hier ook verpest, data was te groot om ingeleerd te worden, testdata was niet genoeg om goede resultaten te krijgen.

[deCube]

Heb opdracht 1 en 3 ingeleverd, ga nu aan opdracht 2 beginnen. Iemand nog tips naast het rekening houden met input waardes van 10^18?

[Megamind]

Dit waren 4 reeksen uit mijn download file:

code:

70413132 123 1 10000000 10000000 20000001 190000000 90000001 360000002
960043019846431759 9999909 9999991 9999949 9999991 879995513 99999488 349999686 549999505
1511881142 123 1 10000000 10000000 1 850000000 360000001 470000002
3 1 3 3 3 1 0 1 1

[deCube]

Thanks, die zal ik eens door mijn script heen gooien zodra die klaar is.

[frG]

Heb nummer 3 maar even gedaan, hoe weet ik of dit nu gelukt is? Heb de files geupload..

[Megamind]

Wachten tot de ronde voorbij is, dan krijg je te horen of je door bent of niet.

[deCube]

Ik heb die input data van Megamind even getest maar met 4GB geheugen haal ik het nog niet... Tijd voor een andere aanpak denk ik.

[frG]

Megamind schreef op zondag 22 januari 2012 @ 15:30:
Wachten tot de ronde voorbij is, dan krijg je te horen of je door bent of niet.

Thanks ben benieuwd, was niet erg lastig iig, als ik het goed begrijp of ik de andere 2 niet perse te doen?

Lijkt me leuk om elkaars code te zien, volgens mij pak ik namelijk niet alles optimaal aan...

[Soultaker]

Lijkt me ook leuk, maar laten we daar even mee wachten tot het einde van de ronde.

[The Flying Dutchman]

Billboards afgerond. Nog eens even kijken of ik de andere twee opdrachten ook ga uitvoeren. Mag in ieder geval door naar de volgende ronde. Nog even afwachten hoeveel tijd ik ga hebben, maar dat zie ik dan wel weer.

[Thralas]

Het is wel jammer dat Facebook hun screwups niet corrigeert. Een uurtje of twee na de start was de billboards challenge opeens een minuut of 10 lang verdwenen. Aangezien ik de pagina in eerste instantie nog niet refreshed had, kon ik de input file alsnog downloaden en begon de timer te lopen.

Helaas bleek de input file leeg en toen de probleempagina weer online was stond er 'Timer expired'. Er zijn meerdere mensen die hierover hun beklag hebben gedaan in de comments, maar noch daarop, noch op het ingevulde feedbackformulier wordt gereageerd.

Afgezien daarvan zijn de problemen best leuk.

[Tharulerz]

Vorig jaar waren er veel meer en ergere screwups, dus bereid je er maar op voor. Rondes die na een uur gewoon stopgezet worden en 1 of 2 weken worden uitgesteld enzo...

[Soultaker]

Vorig jaar werd 't wel met de ronde beter. Dus hopelijk hebben ze hun potje screwups voorlopig gehad.

Ik ben het er wel mee eens dat de communicatie naar de deelnemers toe een stuk beter kan.

[Megamind]

Facebook en communiceren. Zeker nooit met hun API gewerkt...

[Soultaker]

Hehe. Raar dat Facebook zo'n slechte naam heeft bij developers terwijl ze bij gebruikers juist popular zijn. (En wat gebruiken developers zelf dan? Google+?) Of is dit een beetje zoals Microsoft? Iedereen "haat" ze, maar ondertussen draait iedereen wel de nieuwste versie van Windows, Visual Studio, Office et cetera.*

_{* maar niet Internet Explorer. Nooit Internet Explorer.}

[ Voor 41% gewijzigd door Soultaker op 22-01-2012 20:04 ]

[Wolfos]

Waar schrijf ik me in of iets dergelijks? Vond Project Euler ook wel grappig, voordat het te moeilijk werd.

[Soultaker]

Zie linkje in de TS?

[The Flying Dutchman]

Ondertussen ook opdracht 3 ingeleverd, die is verreweg de gemakkelijkste. Alleen na nog wat verder rondneuzen op facebook vond ik de exacte regels (in de FAQ). Daarin staat vermeld dat je source code een single file of gezipped moet zijn. Hopelijk keurt men een tar.gz file ook goed (lijkt me triviaal... maar goed) want ik heb zowel opdracht 1 als opdracht 2 als tar.gz opgestuurd.

Als het me nog lukt om opdracht 2 te voltooien (die is pittig!) dan zal ik die maar even zippen voor alle zekerheid .

[Tharulerz]

Je source code wordt eigenlijk niet nagekeken, tenzij er klachten of bedenkingen zouden komen bij je antwoord (zelfde broncode als iemand anders, etc). Je kan wel anderen hun broncode downloaden op het einde van de ronde, altijd leuk om te kijken.

[deCube]

Is er al iemand die opdracht 2 heeft kunnen voltooien? Ik ben maar gestopt omdat er iets te veel tijd in zou gaan zitten maar ben toch benieuwd.

Heb overigens wel een logica in mijn hoofd zitten voor die opdracht n.a.v. de input data die Megamind heeft verstrekt.

[Soultaker]

Ik heb een oplossing in Python voor Auction die nogal ingewikkeld is en véél te lang duurt (dus niet binnen de zes minuten) maar wel een enigzins zinnige tijdcomplexiteit heeft (O(M log M)). Dat is dus beter dan de oplossingen die 10¹⁸ of 10¹⁴ iteraties nodig hebben (wat natuurlijk nooit gaat lukken).

Ik zal 'm morgen eens in C coden; misschien dat 't dan wel snel genoeg is. Maar misschien moet die log-factor er uit op de een of andere manier.

[The Flying Dutchman]

Ik ben een heel eind met een oplossing voor Auction in C++. Is ook orde grootte iets met M en K . Weet niet of ik dat vanavond nog af krijg. Een belangrijk deel van de oplossing wordt nu in +/- 10 seconden berekend voor een probleem met een N die dichtbij 10^18 ligt en M en K bij 10^7. Maar het is nog niet volledig. Als het me lukt om dat af te krijgen wil ik het eigenlijk nog over de 4 cores van mijn quadcore verdelen... dus dan zou ik ongeveer binnen 1 minuut een oplossing moeten hebben als alle 20 test cases in die orde grootte zijn.

Maar gaat nog vrij veel werk in zitten: dus weet niet of het lukt.

[SaphuA]

Mag je nu na die 6 minuten wel een nieuwe submit doen of heb je maar een kans?

[Soultaker]

Je hebt maar één kans, maar binnen de zes minuten mag je opnieuw insturen; laatste inzending telt.

(Ik heb daar gisteren nog van gebruik van gemaakt nadat ik de invoer van Billboards per ongeluk door mijn oplossing voor Alphabet Soup gehaald had. Dat werkt toevallig, maar levert natuurlijk geen zinnige uitvoer op. Gelukkig viel het me op dat er verdacht veel nullen in de uitvoer zaten. )

[ Voor 9% gewijzigd door Soultaker op 23-01-2012 14:00 ]

[Cartman!]

Megamind schreef op zondag 22 januari 2012 @ 19:56:
Facebook en communiceren. Zeker nooit met hun API gewerkt...

2 jaar geleden had ik het met je eens geweest, maar sinds de Graph API werkt het werkelijk geweldig hoor Alle nieuwe features en depricated functies worden goed gecommuniceerd.

[Soultaker]

The Flying Dutchman schreef op maandag 23 januari 2012 @ 13:14:
Ik ben een heel eind met een oplossing voor Auction in C++. Is ook orde grootte iets met M en K .

Nice; mijn huidige oploessing is O(M×log K) en vast veel ingewikkelder dan de nodig is/de bedoeling was. Twintig officiële testcases kosten nu vier minuten. Kan net, maar verdelen over meerdere cores is wel wenselijk.

Ben wel benieuwd naar jouw aanpak (en je resultaten -- ik weet nog steeds niet 100% zeker of ik alles correct geïmplementeerd heb nu).

[The Flying Dutchman]

Soultaker schreef op maandag 23 januari 2012 @ 15:17:
[...]

Nice; mijn huidige oploessing is O(M×log K) en vast veel ingewikkelder dan de nodig is/de bedoeling was. Twintig officiële testcases kosten nu vier minuten. Kan net, maar verdelen over meerdere cores is wel wenselijk.

Ben wel benieuwd naar jouw aanpak (en je resultaten -- ik weet nog steeds niet 100% zeker of ik alles correct geïmplementeerd heb nu).

Ik ben er nog lang niet... hopelijk lukt het om het vanavond af te ronden. Zal iig na verloop van de deadline even mijn aanpak hier posten.

[SaphuA]

Kon vanmiddag toch niet aan het werk dus maar even oplossingen gesubmit voor Billboards en Alphabet Soup, want die waren het meest eenvoudig. Jammer dat je alleen die paar regeltjes als voorbeeld input hebt om te testen. Even kijken of ik vandaag nog tijd heb om een oplossing voor Auction te submitten.

[Finds]

Als er een vogelbekje bij de scorelijst staat, wilt dat dan zeggen dat je de opdracht ingediend hebt of dat de opdracht correct is? 2 verschillende pagina's op facebook zeggen daar elk iets ander over.

[SaphuA]

Ik snap opdracht 2 niet helemaal...

code:

Item1 is een Bargain als er tenminste een ander item tussenzit waarbij:
Price1<PriceX & Weight1<=WeightX
of
Price1<=PriceX & Weight1<WeightX

En een terrible deal als niet aan een van deze voorwaarden voldaan wordt.

Of...

code:

Een item is een Bargain als:
Price1<Price2..N & Weight1<=Weight2..N
of
Price1<=Price2..N & Weight1<Weight2..N

En een terrible deal als niet aan een van deze voorwaarden voldaan wordt.

Welke is het nu?

[ Voor 47% gewijzigd door SaphuA op 23-01-2012 16:35 ]

[Ulster Seedling]

@SaphuA: Ik heb de volgende logica gebruikt:

spoiler:

Product j is een bargain, tenzij er een product i is waarvoor geldt dat P_j < P_i && W_j <= W_i of W_j < W_i && P_j <= P_i.
Product j is een terrible deal, tenzij er een product i is waarvoor geldt dat P_i < P_j && W_i <= W_j of W_i < W_j && P_i <= P_j.

Dit werkte goed met de testdata. Helaas was mijn code dermate inefficiënt dat ik het niet aan de praat kreeg met de grote dataset voor de echte inzending, dus of het echt helemaal klopt weet ik niet

[Soultaker]

Finds schreef op maandag 23 januari 2012 @ 16:01:
Als er een vogelbekje bij de scorelijst staat, wilt dat dan zeggen dat je de opdracht ingediend hebt of dat de opdracht correct is? 2 verschillende pagina's op facebook zeggen daar elk iets ander over.

Vinkje bedoel je? Dat betekent dat je iets hebt ingestuurd; niet dat het goed is. (No way dat 100 mensen Auction goed hebben. Ik gok hooguit 10.)

jhogervorst schreef op maandag 23 januari 2012 @ 16:36:

spoiler:

Product j is een bargain, tenzij er een product i is waarvoor geldt dat P_j < P_i && W_j <= W_i of W_j < W_i && P_j <= P_i.
Product j is een terrible deal, tenzij er een product i is waarvoor geldt dat P_i < P_j && W_i <= W_j of W_i < W_j && P_i <= P_j.

Mee eens. edit: SaphuA heeft gelijk, i en j moeten ergens omgedraaid worden.

En pro-tip: je kunt UML-tags op GoT ook afsluiten met [/]; dat scheelt een hoop typewerk.

[ Voor 3% gewijzigd door Soultaker op 23-01-2012 17:35 ]

[boe2]

Zelfde ervaring als de rest denk ik: 1 en 3 zijn een eitje, maar die tweede...

[SaphuA]

Moet je Pj en Pi niet juist omdraaien in jouw voorbeeld?

Dus J is een bargain, tenzij er tenminste een ander product is dat goedkoper en lichter is? (Of een daarvan gelijk is).

Edit: Ja dus. Het is allemaal wat vaag geformuleerd, maar ben er uit Het is wat vreemd, omdat een item zowel een Bargan als een Terrible kan zijn.

Edit: Nu moet ik nog een oplossing vinden die niet N*N iteraties nodig heeft. Laat thuis helaas dus hoop dat ik er nog aan toe kom.

[ Voor 51% gewijzigd door SaphuA op 24-01-2012 09:43 ]

[Soultaker]

SaphuA schreef op maandag 23 januari 2012 @ 16:55:
Edit: Nu moet ik nog een oplossing vinden die niet N*N iteraties nodig heeft.

Eerst een oplossing die niet N*N iteraties nodig heeft.
Dan een oplossing die niet N iteraties nodig heeft.
Dan een oplossing die niet lcm(M,K) iteraties nodig heeft.
En dan ben je er waarschijnlijk.

(Maar als ik er geld op moest inzetten denk ik eerlijk gezegd dat het je niet gaat lukken vanavond. )

[pientertje]

Door de modulo heb je nauturlijk wel een periodiciteit. Je hebt dus twee verschillende periodes. Je kunt dus ook de periode berekenen van die twee dingen samen (Kleinste gemene veelvoud??). Dan hoef je slechts een klein deel van het aantal elementen te berekenen. Of zie ik iets over het hoofd?

[ Voor 5% gewijzigd door pientertje op 23-01-2012 22:11 ]

[- peter -]

Nou, dit is best leuk, maar ik dacht slim te zijn met de Auction, omdat daar opeens wel heel erg grote limieten stonden. Wilde de cyclische beweging gebruiken en de resultaten daarvan dan te vermenigvuldigen met het aantal cycli. Werkte perfect op de testset, en ook bij wat grotere getallen werkte het prima. Maar toen ik eenmaal de input file kreeg was het wel erg extreem bij alle waarden en waren de cycli zelf ook in de ordes van 10^16. Tsja.... dat haalde ik niet in 6 minuten en 4GB ram.

spoiler: Auction

Ik dacht de cycli gewoon met M * K te kunnen krijgen?
Maar dan krijg je dus alsnog dit soort getallen:
Total Items: 499587295797208700
One loop has 9257477840542 items
Loops required: 53965
Items left: 7504132359670

Wel erg leuk trouwens! Merk ook dat het fijn programmeren is in Ruby, gaat toch stukken sneller dan C# of Java voor prototypen.

[ Voor 17% gewijzigd door - peter - op 23-01-2012 22:27 ]

[wjzijderveld]

Weet dat ik 0 kans heb o te echt mee te doen (geen ervaring met algoritmes schrijven en tijdgebrek ), maar heb dit maar gebruikt om me op Python te storten.

Net de Alfabet soep ingeleverd, die was wel erg makkelijk. De eerst lijkt ook niet moeilijk, maar of ik hem binnen 2 uur nog afkrijg weet ik niet :-)

[ Voor 0% gewijzigd door wjzijderveld op 23-01-2012 23:11 . Reden: typo ]

[Jegorex]

wjzijderveld schreef op maandag 23 januari 2012 @ 22:45:
WEet dat ik 0 kans heb o te echt mee te doen (geen ervaring met algoritmes schrijven en tijdgebrek ), maar heb dit maar gebruikt om me op Python te storten.

Ik zal ook moeten afhaken zodra je algoritmes nodig zult hebben, maar opdracht 1 en 3 waren prima te doen

[Eärendil]

Ik heb 1 en 3 ook zonder veel problemen opgelost, maar ik had niet genoeg tijd om een oplossing voor de auction opgave te maken.

- peter - schreef op maandag 23 januari 2012 @ 22:22:
Nou, dit is best leuk, maar ik dacht slim te zijn met de Auction, omdat daar opeens wel heel erg grote limieten stonden. Wilde de cyclische beweging gebruiken en de resultaten daarvan dan te vermenigvuldigen met het aantal cycli. Werkte perfect op de testset, en ook bij wat grotere getallen werkte het prima. Maar toen ik eenmaal de input file kreeg was het wel erg extreem bij alle waarden en waren de cycli zelf ook in de ordes van 10^16. Tsja.... dat haalde ik niet in 6 minuten en 4GB ram.

Het lukte mij met random-gegenereerde sample data wel om in acceptabele tijd de cycli van p en w onafhankelijk van elkaar te berekenen. Ik hoopte om met die onafhankelijke cycli analytisch op het eindresultaat te kunnen komen, maar dat lukte nog niet.

SaphuA schreef op maandag 23 januari 2012 @ 16:24:
En een terrible deal als niet aan een van deze voorwaarden voldaan wordt.[/code]

Let op dat het ook een bargain EN een terrible deal kan zijn, zie bijv. case #2 uit het voorbeeld.

[Bolukan]

Kun je de vraagstukken ook ergens lezen, zonder je te hoeven registreren bij Facebook?

zelf iets gevonden

[ Voor 24% gewijzigd door Bolukan op 23-01-2012 23:15 . Reden: Edit: gevonden! ]

[The Flying Dutchman]

Het lukt mij helaas niet meer om Auction op tijd te implementeren. Als ik op zaterdag was begonnen was het waarschijnlijk wel gelukt. De aanpak die ik in gedachten had is als volgt (gezien het uur dat nog rest denk ik niet dat het nu nog iemand lukt om dit te implementeren, maar ik zal het even tussen spoiler tags zetten):

spoiler:

1. Bereken alle prijzen voor de range P1 ... Pm en sla deze op.
2. Bereken alle gewichten voor de range W1 ... Wk en sla deze op.
3. Maak een kopie van alle berekende prijzen en sorteer deze op prijs (zorg dat je de index beschikbaar houdt).
4. Maak een kopie van alle berekende gewichten en sorteer deze op gewicht (zorg dat je de index beschikbaar houdt).
5. Zoek door de prijzen naar de eerste twee opeenvolgende prijzen die gelijk zijn: dit is een collission.
6. Zoek door de gewichten naar de eerste twee opeenvolgende gewichten die gelijk zijn: dit is een collission.
7. Vaak zal een collission voorkomen tussen P1 en PM, maar het is bijvoorbeeld ook mogelijk dat er ergens middenin de range de condities plotseling zo veranderen dat je een veel kortere repeterende serie krijgt (voorbeeld: 5, 4, 7, 8, 6, 3, 6, 3, 6, 3, 6, 3).
8. Nu weet je precies hoe de prijzen en de gewichten zichzelf herhalen in de range 1 ... N (terwijl je alleen de prijzen voor 1 ... M en de gewichten voor 1 ... K berekend hebt).
9. Voor de bargain: zoek naar het object het de laagste prijs (eenvoudig: je hebt de gesorteerde lijst op prijs nog).
10. Zoek nu het object dat dezelfde prijs heeft en een zo laag mogelijk gewicht (dit kan eenvoudig doordat de reeksen zich herhalen). Het gewicht dat hieruit komt is het maximum gewicht dat een bargain kan hebben (immers... we zoeken het laagste gewicht voor het allergoedkoopste object; dus een object met een hoger gewicht kan niet een lagere prijs hebben).
11. Doorloop nu alle objecten die een lager gewicht hebben dan het gevonden maximum gewicht: begin bij het lichtste object. Als dit object minder zwaar is dan het maximum gevonden gewicht: dan is dit ook een bargain. Onthoudt de laagste prijs van dit object: dit wordt de maximum prijs.
12. Zoek nu naar steeds iets zwaardere objecten tot je het maximum gewicht bereikt hebt. Als je een object vind en het is goedkoper dan de gevonden maximum prijs: dan is het een bargain. Pas de maximum prijs nu aan, aan het gevonden object.
13. Hieruit volgt een serie objecten die allemaal bargains zijn. Nu moet er nog gekeken worden of deze objecten misschien dubbel voorkomen in de gehele range. De dubbele entries zijn ook allemaal bargains.
14. Doe nu iets soortgelijks, maar dan andersom voor terrible deals.

Mijn stappen 10 en 11 waren nog te langzaam geimplementeerd... stel dat ik een laagste prijs had gevonden op P34 en ik weet dat de range zich iedere 20 stappen herhaald, dan doorzocht ik alle P34+20X die kleiner zijn dan PN. Maar bij hele grote ranges kunnen dat nog steeds 100 miljoen opties zijn die je moet bekijken. Dat schiet niet op.

Waarschijnlijk handiger is om door de gesorteerde lijst met gewichten te gaan, te kijken naar de bijbehorende index... en vervolgens uit te rekenen of dit gewicht ergens binnen de range N samenvalt met de prijs. Zo vind je veel sneller het laagste gewicht bij een gegeven prijs.

Daarnaast moest ik de terrible deals ook nog implementeren... maar dat is feitelijk hetzelfde behalve dat je een aantal zaken omdraaid.

[Vaan Banaan]

Bolukan schreef op maandag 23 januari 2012 @ 23:06:
Kun je de vraagstukken ook ergens lezen, zonder je te hoeven registreren bij Facebook?
zelf iets gevonden

Ik heb ook geen Facebook account, leuk om de opdrachten toch nog te kunnen lezen!
Omdat PasteBin schijnbaar geen opmaak heeft, wordt bij opdracht 2 de formule verkracht. Daar had ik even wat tijd voor nodig om te begrijpen wat er staat.
Pi = ((A*Pi-1 + B) mod M) + 1 (for all i = 2..N)
Wi = ((C*Wi-1 + D) mod K) + 1 (for all i = 2..N)
Correct me if i'm wrong. Handig die [/]-tag, bedankt voor de tip Soultaker
If product i has price P_i and weight W_i then the following holds for product i+1:
P_i = ((A*P_i-1 + B) mod M) + 1 (for all i = 2..N)
W_i = ((C*W_i-1 + D) mod K) + 1 (for all i = 2..N)

[Eärendil]

The Flying Dutchman schreef op maandag 23 januari 2012 @ 23:56:

1. Bereken alle prijzen voor de range P1 ... Pm en sla deze op.
2. Bereken alle gewichten voor de range W1 ... Wk en sla deze op.
3. Maak een kopie van alle berekende prijzen en sorteer deze op prijs (zorg dat je de index beschikbaar houdt).
4. Maak een kopie van alle berekende gewichten en sorteer deze op gewicht (zorg dat je de index beschikbaar houdt).
5. Zoek door de prijzen naar de eerste twee opeenvolgende prijzen die gelijk zijn: dit is een collission.
6. Zoek door de gewichten naar de eerste twee opeenvolgende gewichten die gelijk zijn: dit is een collission.
7. Vaak zal een collission voorkomen tussen P1 en PM, maar het is bijvoorbeeld ook mogelijk dat er ergens middenin de range de condities plotseling zo veranderen dat je een veel kortere repeterende serie krijgt (voorbeeld: 5, 4, 7, 8, 6, 3, 6, 3, 6, 3, 6, 3).
8. Nu weet je precies hoe de prijzen en de gewichten zichzelf herhalen in de range 1 ... N (terwijl je alleen de prijzen voor 1 ... M en de gewichten voor 1 ... K berekend hebt).
9. Voor de bargain: zoek naar het object het de laagste prijs (eenvoudig: je hebt de gesorteerde lijst op prijs nog).
10. Zoek nu het object dat dezelfde prijs heeft en een zo laag mogelijk gewicht (dit kan eenvoudig doordat de reeksen zich herhalen). Het gewicht dat hieruit komt is het maximum gewicht dat een bargain kan hebben (immers... we zoeken het laagste gewicht voor het allergoedkoopste object; dus een object met een hoger gewicht kan niet een lagere prijs hebben).
11. Doorloop nu alle objecten die een lager gewicht hebben dan het gevonden maximum gewicht: begin bij het lichtste object. Als dit object minder zwaar is dan het maximum gevonden gewicht: dan is dit ook een bargain. Onthoudt de laagste prijs van dit object: dit wordt de maximum prijs.
12. Zoek nu naar steeds iets zwaardere objecten tot je het maximum gewicht bereikt hebt. Als je een object vind en het is goedkoper dan de gevonden maximum prijs: dan is het een bargain. Pas de maximum prijs nu aan, aan het gevonden object.
13. Hieruit volgt een serie objecten die allemaal bargains zijn. Nu moet er nog gekeken worden of deze objecten misschien dubbel voorkomen in de gehele range. De dubbele entries zijn ook allemaal bargains.
14. Doe nu iets soortgelijks, maar dan andersom voor terrible deals.

Ik dacht in dezelfde richting. Ik probeerde al tijdens stap 1 en 2 de collissions te vinden, zodat ik niet helemaal tot M en K hoefde te rekenen (ten koste van extra zoeken in die eerste stappen). Als P_i gelijk is aan P_i-x zal de hele serie daartussen de hele tijd herhaald worden, want de parameters A, B en M veranderen niet.

[wjzijderveld]

Helaas heb ik ook Billboard niet af gekregen, maar was wel leuk er mee bezig te zijn.
Ga Billboard ook nog wel afmaken, maar nu eerst naar bed :-)

edit:
edit: En nu heb ik hem wel (Denk ik iig, kan de input niet meer testen nu), testresultaten kloppen nu in ieder geval.
Oh ja, ik ging slapen

[ Voor 34% gewijzigd door wjzijderveld op 24-01-2012 01:26 ]

[pientertje]

Mijn oplossingen:

Billboards
http://pastebin.com/sbP7ECmN
Auction (N*N)
http://pastebin.com/HEJrYVMY
Letter Soup
http://pastebin.com/tSu9nXrt

[The Flying Dutchman]

Eärendil schreef op dinsdag 24 januari 2012 @ 01:06:
[...]

Ik dacht in dezelfde richting. Ik probeerde al tijdens stap 1 en 2 de collissions te vinden, zodat ik niet helemaal tot M en K hoefde te rekenen (ten koste van extra zoeken in die eerste stappen). Als P_i gelijk is aan P_i-x zal de hele serie daartussen de hele tijd herhaald worden, want de parameters A, B en M veranderen niet.

Dat klopt, maar als je dan toch tot M moet rekenen omdat daarvoor geen collission voorkomt dan is jouw methode denk ik minder efficient. Stappen 1 t/m 9 ging bij mij in 10-20 seconden voor een probleem met M en K dichtbij het maximum (enkele core van een AMD Phenom 9750 x4, vrij langzaam beestje dus ook).

[boe2]

Had er maar 2 opgelost:
Lettersoup was eenvoudig. Tel gewoon hoeveel keer iedere letter voorkomt, laagste cijfer is het aantal dat je zoekt.
Bij Billboard ben ik brute-force alle groottes afgegaan. Niet erg elegant maar perfect doenbaar gezien de constraints.

[SaphuA]

@Boeboe, ook rekening gehouden dat de c er 2x in zit?

Ben gister niet meer toegekomen aan die auction, maar denk niet dat het me gelukt zou zijn.

Score van 2; betekent dat dat je door bent? Ben benieuwd of er iemand die auction goed heeft

[ Voor 43% gewijzigd door SaphuA op 24-01-2012 09:21 ]

[wjzijderveld]

Zie nu opeens dit staan:

quote: Facebook

For the qualification round, you just need one correct problem to advance.

Mogelijk dat ik toch nog een kans krijg om de volgende ronde te zien dus :-)

[The Flying Dutchman]

De problemen voor ronde 1 van de 2011 versie staan ook nog steeds online. Leuk om eens even te kijken en een feeling te krijgen voor de moeilijkheid van problemen in ronde 1.

Zie helemaal onderaan bij de FAQ:
https://www.facebook.com/...php?round=144428782277390

[frG]

Het lijkt wel of ik de enige ben die bij de lettersoup een andere (minder effectieve?) aanpak heeft gebruikt.

Ik probeerde uit alle letters het woord te spellen als ik dan bij de P was deed ik +1 (als een letter erinzat, werd deze uit de lijst geremoved), en als een letter niet meer bestond dan was ik klaar.

[deCube]

Mijn aanpak was hetzelfde als die van Boeboe, waarbij ik het aantal van letter "C" door de helft deed en naar beneden afrondde.

Voor Billboards checkte ik d.m.v. een loop over hoeveel regels alle woorden zouden passen, rekening houdend met spaties, met "hoogte / aantal regels" als breedte van de karakters.

[ Voor 41% gewijzigd door deCube op 24-01-2012 09:34 ]

[wjzijderveld]

Bij deze mijn aanpak voor de Alphabet Soup:
http://pastebin.com/4CzjYPP0

getInputPath() geeft gewoon het pad naar de map waar ik de input bestanden plaatste (met als parameter of het de test versie of definitieve versie is).

Disclaimer: Eerste Python programma, zal ongetwijfeld ergens dingen gebruikt hebben die niet verstandig zijn :-)

edit: Billboard programma: http://pastebin.com/HjNGmvre Ook hier zullen vast fouten in zitten

[ Voor 12% gewijzigd door wjzijderveld op 24-01-2012 09:40 ]

[SaphuA]

Slechts 160 van de 7500 deelnemers hebben een goed resultaat voor auction opgeleverd (van de huidige resultaten).

Klopt idd niet Dacht dat de grijze vinkjes al betekende dat het goed was.

[ Voor 27% gewijzigd door SaphuA op 24-01-2012 11:05 ]

[The Flying Dutchman]

SaphuA schreef op dinsdag 24 januari 2012 @ 09:48:
Slechts 160 van de 7500 deelnemers hebben een goed resultaat voor auction opgeleverd (van de huidige resultaten).

Waar zie je dat? Ik zag zojuist alleen nog maar grijze vinkjes...

Ik vroeg me nog sterk af of het niet mogelijk was om die formule te vereenvoudigen zodat hij niet meer afhankelijk is van Pi-1. Maar met mijn wiskunde kennis kwam ik daar niet binnen een paar uurtjes uit (plus dat het maar de vraag is of dat je iets zou opleveren mbt het oplossen van het probleem).

[MrHaas]

Mijn aanpak:

• A = A % M, B = B % M, scheelt weer wat performance.
• Bereken prijzen P1..Pa-1 tot Pa in P1..Pa-1 zit en sla de index i op van de match. Je hebt dan alle mogelijke prijzen (a <= M). De i sla je op zodat je later de positie van elke prijs terug kunt vinden.
• Zelfde voor W
• Functie die bepaalt of de combinatie (P, W) bestaat mbv van Extended Euclides.
• Voor de bargains: neem laagste P, zoek de laagste W met bv van bovenstaande functie. Ga naar volgende P en zoek weer de laagste W die niet hoger of gelijk mag zijn dan de vorige W. Ga zo door tot je een P hebt die matcht met de laagste W of totdat je alle P's hebt gehad.
• Voor de terribles: zelfde als bovenstaande, maar dan hoogste P, hoogste W.
• Bepaal hoe vaak elke bargain en terrible voorkomt.

Helaas zat er nog een foutje in de code op het moment dat ik m runde, namelijk dat ik alleen keek of Pn gelijk was aan P0 voor het bepalen van het patroon. Geen genoeg tijd gehad in die 6 minuten om het te fixen. Daarna niet meer geprobeerd te fixen, maar mss dat ik 't deze week nog ff probeer.

[The Flying Dutchman]

MrHaas schreef op dinsdag 24 januari 2012 @ 10:41:
Mijn aanpak:

• A = A % M, B = B % M, scheelt weer wat performance.
• Bereken prijzen P1..Pa-1 tot Pa in P1..Pa-1 zit en sla de index i op van de match. Je hebt dan alle mogelijke prijzen (a <= M). De i sla je op zodat je later de positie van elke prijs terug kunt vinden.
• Zelfde voor W
• Functie die bepaalt of de combinatie (P, W) bestaat mbv van Extended Euclides.
• Voor de bargains: neem laagste P, zoek de laagste W met bv van bovenstaande functie. Ga naar volgende P en zoek weer de laagste W die niet hoger of gelijk mag zijn dan de vorige W. Ga zo door tot je een P hebt die matcht met de laagste W of totdat je alle P's hebt gehad.
• Voor de terribles: zelfde als bovenstaande, maar dan hoogste P, hoogste W.
• Bepaal hoe vaak elke bargain en terrible voorkomt.

Helaas zat er nog een foutje in de code op het moment dat ik m runde, namelijk dat ik alleen keek of Pn gelijk was aan P0 voor het bepalen van het patroon. Geen genoeg tijd gehad in die 6 minuten om het te fixen. Daarna niet meer geprobeerd te fixen, maar mss dat ik 't deze week nog ff probeer.

Grotendeels dezelfde aanpak die ik ook had. Liep gisteravond vast op het vinden van de laagste P bij een gegeven W. Had in de gaten dat ik dat de berekening moest doen ipv zoeken, maar het lukte gisteravond om 22.00u niet meer om op tijd die berekening te vinden (plus dat er sowieso nog een hoop geimplementeerd moest worden).

[Soultaker]

Ik heb mijn aanpak hier uitgelegd.

Code voor het Auction probleem publiceer ik als ik heb kunnen verifiëren dat 'ie correct is. Heeft iemand anders 'm nog weten op te lossen, zodat we resultaten kunnen vergelijken?

[Soultaker]

MrHaas schreef op dinsdag 24 januari 2012 @ 10:41:
Mijn aanpak:

• A = A % M, B = B % M, scheelt weer wat performance.
• Bereken prijzen P1..Pa-1 tot Pa in P1..Pa-1 zit en sla de index i op van de match. Je hebt dan alle mogelijke prijzen (a <= M). De i sla je op zodat je later de positie van elke prijs terug kunt vinden.
• Zelfde voor W
• Functie die bepaalt of de combinatie (P, W) bestaat mbv van Extended Euclides.

Dit is een leuke aanpak. Als ik het goed zie zou dat ook een O(M log K) oplossing moeten opleveren.

De details zijn nog wel lastig; je hebt bijvoorbeeld nog een manier nodig om uit te rekenen hoe vaak een product voorkomt. En kun je het algoritme van Euclides wel gebruiken als N < K (waardoor dus een deel van de oplossingen van de RNG niet daadwerkelijk gegenereerd worden)?

[SaphuA]

Nette blogpost Soultaker (Twee //'s teveel in je linkje btw!) Had zelf helaas geen tijd meer gehad om die random formule en de relatie tussen price/weight uit te pluizen.

[ Voor 11% gewijzigd door SaphuA op 24-01-2012 12:31 ]

[Soultaker]

Ah, ik had wél een goede (protocol-relatieve) link getypt maar blijkbaar verprutst de forumsoftware 'm door er alsnog http:// voor te zetten. (Firefox opent 'm dan stiekem wel, waardoor het me niet opgevallen was.) Kan ik mooi aan m'n feature request/bug report toevoegen.

[Jegorex]

De resultaten zijn bekend en ik ben door naar de volgende ronde

edit
Ik was eerst 5000 ofzo en nu 1817

[ Voor 24% gewijzigd door Jegorex op 24-01-2012 20:53 ]

[Megamind]

Ik ook, stond vanochtend nog op plaats 2001, nu op 1079, zijn er toch behoorlijk wat afgevallen dan! Had trouwens beide goed.

Toch vet om te zien dat maar 22 mensen de tweede opdracht goed hebben gemaakt.

[Soultaker]

Ik tel er sowieso al 28 en dat is meer dan ik verwacht had! Gaat nog moeilijk worden in de komende ronden.

(Ik zie ook twee personen die Alphabet Soup gefaald hebben maar wél Auction goed hebben opgelost. Hoe je dat voor elkaar krijgt... )

Plaatsen op de ranglijst zeggen nu natuurlijk nog niet zoveel, aangezien duizenden mensen twee problemen hebben opgelost maar niemand op dezelfde tijd is begonnen.

[The Flying Dutchman]

Zowel billboards als alphabetsoup goed. Toch jammer dat het niet gelukt is een poging te doen met auction. Misschien dat ik die nog af ga maken in voorbereiding op de komende ronde. Ben erg benieuwd naar de komende opdrachten.

[Corniel]

Soultaker schreef op dinsdag 24 januari 2012 @ 21:13:

Ik zie ook twee personen die Alphabet Soup gefaald hebben maar wél Auction goed hebben opgelost. Hoe je dat voor elkaar krijgt... (..)

Nou dat lijkt me niet zo moeilijk. Je doet goed je best op Auction, hebt nog weinig tijd over om de Alpahbet Soup te maken een faalt jammerlijk.

Maar goed. Ik had het heel druk maandag (toen ik zag dat de wedstrijd was). Las dat twee heel lastig was en kon zo snel geen goede oplossing verzinnen. Toen heb ik drie niet meer proberen te maken.

Succes aan allen die verder zijn gekomen. (met een oplossing ingeleverd ga ik er maar even van uit dat ik er niet meer tussenzit)

[wjzijderveld]

Wauw, ik heb het zelfs voor elkaar gekregen de Alphabet Soup te verprutsen
Iemand enige idee wat de valkuil was die ik blijkbaar over het hoofd heb gezien? Ik hield wel rekening met de dubbele C. Resultaat test-input klopte uiteraard gewoon.

[Eärendil]

Het probleem is dat je er niet goed genoeg rekening mee houdt dat de 'C' twee keer in "HACKERCUP" zit.

Python:

def hasResult(dictionary):
    usedLetters = {}
    # Loop thru letters in testString
    for letter in list("HACKERCUP"):
        # If letter not in string or no longer in dictionary, return false
        if letter not in dictionary or dictionary[letter] <= 0:
            return False
        else:
        # else add letter to usedLetters to make the delta later on 
            if letter not in usedLetters:
                usedLetters[letter] = 1
            else:
                usedLetters[letter] += 1
            
    # Word found, perform delta
    for foundLetter in usedLetters:
        dictionary[foundLetter] -= 1
    
    return True

Je bedoelde waarschijnlijk:

Python:

    # Word found, perform delta
    for foundLetter in usedLetters:
        dictionary[foundLetter] -= usedLetters[foundLetter]

Maar dat gaat nog steeds mis als er een oneven aantal 'C's in zit (de check dictionary[letter] <= 0 in regel 6 wordt altijd uitgevoerd op de nog niet aangepaste dictionary)

Dit werkt wel:

Python:

def hasResult(dictionary):
    usedLetters = {}
    # Loop thru letters in testString
    for letter in "HACKERCUP":
        # If letter not in string or no longer in dictionary, return false
        if letter not in dictionary or dictionary[letter] <= 0:
            return False
        else:
        # subtract letter from dictionary
            dictionary[letter] -= 1
    
    return True

---

Nog een paar tips:

Python:

    while hasResult(dictionary):
        result += 1

in plaats van:

Python:

    while True:
        if hasResult(dictionary):
            result += 1
        else:
            break

---

Python:

for letter in "HACKERCUP":

kan ook in plaats van:

Python:

for letter in list("HACKERCUP"):

[ Voor 10% gewijzigd door Eärendil op 25-01-2012 02:18 ]

[frG]

Corniel schreef op dinsdag 24 januari 2012 @ 22:58:
[...]

Nou dat lijkt me niet zo moeilijk. Je doet goed je best op Auction, hebt nog weinig tijd over om de Alpahbet Soup te maken een faalt jammerlijk.

Maar goed. Ik had het heel druk maandag (toen ik zag dat de wedstrijd was). Las dat twee heel lastig was en kon zo snel geen goede oplossing verzinnen. Toen heb ik drie niet meer proberen te maken.

Succes aan allen die verder zijn gekomen. (met een oplossing ingeleverd ga ik er maar even van uit dat ik er niet meer tussenzit)

Doe is je website nakijken.. kreeg een melding van malware voor corniel.nl

[Ghehe]

frG schreef op woensdag 25 januari 2012 @ 00:47:
[...]
Doe is je website nakijken.. kreeg een melding van malware voor corniel.nl

Je bent niet alleen, Google Chrome was hier ook moord en brand aan het schreeuwen.

---

On topic: Ik ben door naar de volgende ronde. Feestje bouwen (Maar ik ga vooral een feestje bouwen omdat mijn examens er sinds vandaag opzitten en dat was weeral off-topic )

[- peter -]

Jep, ik ben ook door met 2 goede oplossingen, behalve natuurlijk auction. Wel meesterlijk uitgebreide code hebben die oplossingen nodig zeg. Denk dat als je die goed hebt, je de rest ook wel aankan.

[Wolfboy]

Hrm... zo te zien krijg je score per goed opgeloste opdracht? Misschien had ik er dan toch iets meer tijd in moeten steken

Ik heb gisteren de alphabet soup in 20min in elkaar geprutst en de rest verder maar laten zitten.

[Tharulerz]

Wolfboy schreef op woensdag 25 januari 2012 @ 04:22:
Hrm... zo te zien krijg je score per goed opgeloste opdracht? Misschien had ik er dan toch iets meer tijd in moeten steken

Ik heb gisteren de alphabet soup in 20min in elkaar geprutst en de rest verder maar laten zitten.

Scores worden niet overgedragen naar de volgende ronde, dus ik zie niet in wat het uitmaakt.

Volgende ronde gaan wel slechts de beste 500 door, dus daar kan je best wel zoveel mogelijk oplossen (dan gaat het van 5947 naar 500, dat gaat snel zeg... vorig jaar ging het veel trager )

[wjzijderveld]

Eärendil schreef op woensdag 25 januari 2012 @ 00:28:
Het probleem is dat je er niet goed genoeg rekening mee houdt dat de 'C' twee keer in "HACKERCUP" zit.

[..]

Ah, uiteraard. Weet ook wel beetje hoe het komt. Had gewoon niet voor Python moeten kiezen
Door Python was ik al blij dat het werkte en testresultaten klopte, en ik redelijk het idee had geen hele rare dingen had gedaan in Python. Had verder moeten kijken dan me neus lang is.

Nog een paar tips:

Thanks!

[Wolfboy]

Tharulerz schreef op woensdag 25 januari 2012 @ 06:40:
[...]

Scores worden niet overgedragen naar de volgende ronde, dus ik zie niet in wat het uitmaakt.

Volgende ronde gaan wel slechts de beste 500 door, dus daar kan je best wel zoveel mogelijk oplossen (dan gaat het van 5947 naar 500, dat gaat snel zeg... vorig jaar ging het veel trager )

Ah nice

Dat hoopte ik al, ik zie de regels alleen nergens online staan. Had weinig zin om veel tijd in de kwalificatieronde te steken.

[Corniel]

Shit, nu heb ik me dus gekwalificeerd, nu moet ik alsnog meedoen van mezelf...

Ik moet Sjaakie eens verbieden om mij op dit soort wedstrijden te attenderen...

[Soultaker]

Facebook heeft hier de officiële oplossingen van de problemen toegelicht. Auction had in O(M + K) gekund door op volgorde door de cycle van gewichten te lopen.

[wjzijderveld]

Heb zojuist Billboard nog gesubmit en die was wel goed... Best jammer, als ik die namelijk 20 minuten eerder klaar had, was ik dus wel een ronde verder

[dossiewossie]

Hmm.. Vorige week voor het eerst een perl script geschreven. Afgelopen maandag zag ik dit topic, en deed een poging om alphabet soup tot een goed einde te brengen. Bijna gelukt, als ik even had bedacht dat er 2 C`s in HACKERCUP zitten ;-)

Nu heb ik billboard gemaakt, maar als ik het goed begrijp is er geen manier meer om te checken of ik het goed heb gedaan? Je kan nog wel iets uploaden, maar vervolgens gebeurt er niets. Daarnaast lijkt het mij leuk om de perl inzendingen te bekijken van andere deelnemers, maar hoe haal ik die eruit? Ik vrees het ergste, jammer, want ik vind dit eigenlijk wel een leuke manier om de taal een beetje onder de knie te krijben

Mijn script heb ik hier iig even neergegooid

[Soultaker]

Die practice mode van Facebook werkt wel, maar niet 100% betrouwbaar. Gewoon nog een keer submitten als het niet werkt. (Volgens mij gaat het mis omdat de pagina automatisch refresht. Als je aan het submitten bent tijdens een refresh dan krijg je het resultaat niet te zien.)

Je scriptje ziet er trouwens netjes uit voor iemand die nog nooit eerder in Perl geprogrammeerd heeft, maar het algoritme klopt niet helemaal.

Problematische gevallen zijn bijvoorbeeld:

10 100 abcdefghijk

Jij print 1, maar het moet 0 zijn. En:

50 20 a b c d e f

Jij print 9, maar het moet 10 zijn.

Ik laat het aan jou om de fouten in je code te vinden.

[ Voor 20% gewijzigd door Soultaker op 26-01-2012 18:04 ]

[dossiewossie]

Thanx, hier kan ik wat mee!

Probleem 1 is iig duidelijk, ik had hier helemaal overheen gelezen:

If the text does not fit when printed at a size of 1", then output 0.

Probleem 2 zie ik even niet zo snel. Vanavond geen tijd meer, maar ik kom hier morgen op terug

[Bolukan]

Soultaker schreef op donderdag 26 januari 2012 @ 18:02:

50 20 a b c d e f

Jij print 9, maar het moet 10 zijn.

Hoe kan dat 10 zijn?

Edit: O het is natuurlijk 50 20 en niet 20 50.

[ Voor 10% gewijzigd door Bolukan op 26-01-2012 20:57 ]