Facebook Hacker Cup

[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 ]

[dossiewossie]

Soultaker schreef op donderdag 26 januari 2012 @ 18:02:
Ik laat het aan jou om de fouten in je code te vinden.

Ik heb de fout gevonden Het probleem was de berekening van de approximate font size:

Perl:

my $fsize   = floor(sqrt(($w*$h)/(length(join(' ',@values))))); #approximate font size

De eerste fout was het gebruik van floor, terwijl ceil veel mee voor de hand ligt. Als ik dat aanpas, dan kreeg ik wel de juiste resultaten met het door jouw gegeven voorbeeld:

code:

50 20 a b c d e f

Dit print nu netjes 10 ipv 9. Het probleem lag in het feit dat mijn geschatte font-size geen rekening hield met 2 invloeden op de font-size, die de daadwerkelijke code daarna wel heeft. Namelijk:

1 - Houd geen rekening met het wegvallen van spaties aan het einde van een zin. Daardoor wordt er minder ruimte gebruikt, waardoor de werkelijke font-size groter wordt dan de geschatte font-size.

2 - Houd geen rekening met het niet afbreken van woorden. Daardoor wordt er ruimte niet gebruikt voor karakters, waardoor de werkelijke font-size kleiner wordt dan de geschatte font-size.

Over het algemeen heeft 2 meer invloed dan 1, waardoor de geschatte font grootte iets hoger ligt dan de werkelijke font grootte, echter in jou voorbeeld heeft 2 geen invloed, maar 1 des te meer. Met ceil ging het dus wel goed, maar daarna ben ik voorbeelden gaan verzinnen die evengoed nog fout konden gaan.

code:

30 40 aba a a aba a a

Met ceil wordt er toch 9 geprint ipv het juiste getal 10 (de schatting is 8.9 oid). Daarna heb ik nagedacht hoe ik de berekening kon verbeteren, maar daar kwam ik niet uit.

Dus toen even googlen, en ik kwam uit op deze oplossing, geschreven in python. Hier wordt ook een schatting gemaakt, maar op een andere manier, namelijk de breedte delen door het aantal karakters van het langste woord. Stel de breedte is 30, en het langste woord is ook 30, dan is de geschatte font grootte 1, wat ook klopt. Uiteindelijk is de schatting dus geworden:

Perl:

my $fsize = ceil($w/(max(map(length,@values)))); #approximate font size

Dit werkt wel, maar heeft als nadeel dat de geschatte waarde soms ver af ligt van de eigenlijk waarde, waardoor er toch veel iteraties nodig zijn.

Ik vraag mij af of mijn oorspronkelijke manier is aan te passen zodat deze wel klopt? Want die zit er altijd erg dichtbij.

Bedankt voor het de juiste richting op duwen soultaker, ik zal eens kijken naar auction, maar ik vrees dat die te hoog gegrepen is

Code staat hier .

offtopic:
En ik zal nog even testen in practice mode of hij nu wel klopt, das nog niet zeker.

[Jegorex]

Congratulations!

You have advanced to round 1 of the 2012 Hacker Cup! The round will start on Saturday, January 28th at 10:00 PST and will last 24 hours. To see the start time in your local time zone, please click here.

The top 500 competitors will advance to round 2. In addition, anyone who correctly solves as many problems as the competitor in 500th place will also advance to round 2.

Best of luck and happy hacking,
The Hacker Cup Team

Het begint zaterdag 19:00 Nederlandse tijd.

[ Voor 10% gewijzigd door Jegorex op 27-01-2012 19:43 ]

[MrHaas]

Toch m'n oplossing voor auction nog gefixt in Python. Moest nog meer aan gebeuren dan ik hoopte :):
http://pastebin.com/70UPMKPy
Doet er op mijn laptop zo'n 2 minuten over in PyPy en 4 minuten in CPython 2.7.

Mooie oefening voor morgen.

[Soultaker]

@MrHaas: nette code, maar wat is de tijdcomplexiteit van die oplossing?

Op de officiële testdata heeft 'ie hier 3 uur (!) nodig (met uitschieters van een half uur per testcase) weliswaar met CPython 2.6.2 maar op een behoorlijk snel systeem. Ik zie dus niet hoe jij op 4 minuten uitkomt... of ik doe iets verkeerd, of jij.

[MrHaas]

Soultaker schreef op zaterdag 28 januari 2012 @ 18:02:
@MrHaas: nette code, maar wat is de tijdcomplexiteit van die oplossing?

Op de officiële testdata heeft 'ie hier 3 uur (!) nodig (met uitschieters van een half uur per testcase) weliswaar met CPython 2.6.2 maar op een behoorlijk snel systeem. Ik zie dus niet hoe jij op 4 minuten uitkomt... of ik doe iets verkeerd, of jij.

Hmm, zie wel dat ie veel geheugen gebruikt. Als ik m multiprocess gaat ie als een malle lopen swappen. Als ik m op serieel draai, piekt ie soms over de 5gig heen. Weet niet hoeveel RAM je hebt?

[Soultaker]

64 GB. Dat lijkt me het probleem niet.

Run 'm eens op een testcase als:

905104693315080537 9999909 9999991 9999949 10000000 649996686 729996274 470000001 920000002

edit:
Misschien beter om dit ná de wedstrijd uit te zoeken. Alvast veel succes, allemaal!

[ Voor 161% gewijzigd door Soultaker op 28-01-2012 18:49 ]

[MrHaas]

Soultaker schreef op zaterdag 28 januari 2012 @ 18:47:
64 GB. Dat lijkt me het probleem niet.

Run 'm eens op een testcase als:

905104693315080537 9999909 9999991 9999949 10000000 649996686 729996274 470000001 920000002

edit:
Misschien beter om dit ná de wedstrijd uit te zoeken. Alvast veel succes, allemaal!

Hehe, dat moet idd genoeg zijn, hier 8GB. Als ik die run:

Case #1: 9051 9051
Function main finished in 19.369376s

Verder heb ik ze alleen gerund op de inputfile die ik van FB kreeg.

Succes!

[Soultaker]

Huh, vreemd. Dat lijkt me wel het goede antwoord.

Kun je trouwens je algoritme toelichten? Als 'ie correct werkt (waar ik dus niet 100% van overtuigd ben, momenteel, maar OK ) is de code wel elegant (helemaal als je bedenkt dat je nog vrij veel "dubbele" code er in hebt zitten). En je lijkt geen ingewikkelde datastructuren nodig te hebben.

[ Voor 9% gewijzigd door Soultaker op 28-01-2012 19:06 ]

[Ghost(NL)]

Jammer dat ik het nu pas lees, had het wel leuk gevonden om het ook te proberen.

Maar goed, ik zat een beetje te lezen door de oplossingen, met name van billboard, welke door de meeste als lastigste werd ervaren. Nu zie ik eigenlijk bij de meeste oplossingen mensen testen vanaf font-size 1 tot het maximum. Oftewel testen tot het niet meer past.

Waar ik nu benieuwd naar ben, is er iemand die andersom heeft geredeneerd? Dus eerst het absolute maximum bepalen en terug rekenen naar de eerste die wel past?

Toen ik namelijk de probleem stelling las en daaruit begreep dat de fontheight gelijk zou staan aan de fontwidth kwam ik op het volgende idee:

Als ik nu de gegeven width * height doe en deel door lengte van de input en van het resultaat de wortel neem, dan heb ik afgerond de absolute maximale size van het font op het gegeven billboard en de gegeven input, waarbij ik geen rekening houd met het niet mogen breken van woorden.

Het niet breken van woorden heeft m.i. altijd tot gevolg dat de fontsize lager uitvalt omdat je 'inefficient' met de ruimte om gaat. Dus je werkelijke max size op basis van de probleemstelling ( woorden mogen niet gebroken worden ) valt dan volgens mij dan altijd lager uit?

Als ik bovenstaande 'formule': sqrt((width*height)/length) gebruik op de voorbeelden van hier:

http://pastebin.com/jPHiJRBa

20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup

Geeft me dat als absolute max ( afgerond per case:

sqrt((20*6)/10) = 3, uiteindelijke antwoord 3
sqrt((100*20)/15)= 11, uiteindelijke antwoord 10
sqrt((10*20)/20)= 3, uiteindelijk antwoord 2
sqrt((55*25)/12)= 10, uiteindelijke antwoord 8
sqrt((100*20)/24)=9, uiteindelijke antwoord 7

Hiermee neemt je aantal itteraties af en zeker met grote(re) billboards heb je dan sneller je oplossing. Nu weet ik eerlijk gezegd niet of snelheid een eis was, maar vond het wel een leuke probleemstelling om eens te bekijken.

En ik ben dus, zoals gezegd, benieuwd of iemand dit als de basis van zijn oplossing heeft gebruikt?

( Ik zie nu een oplossing waar iemand het in ieder geval deels zo doet even verder lezen hoe hij het oplost )

[The Flying Dutchman]

Billboard werd zeker niet als lastigste beschouwd, dat was Auction.
Mijn aanpak bij billboard was:

- tel het minimum aantal characters nodig (alle woorden zonder spaties).
- kijk hoe je het bord kunt verdelen in vlakken (die elk 1 character kunnen bevatten), bijvoorbeeld voor een 100x50 bord zou je met font size 10 10x5 vlakken krijgen.
- begin bij de grootste fontsize die qua vlakverdeling voldoet aan het minimum aantal characters
- probeer te vullen, als dat niet lukt ga dan 1 fontsize kleiner

[Finds]

De nieuwe problemen staan online! Heb ze net even overlopen en 1 en 3 lijken mij op het eerste zicht relatief doenbaar. Denk persoonlijk dat de tweede 'Recover the Sequence' de moeilijkste gaat zijn.

Zou me verbazen dat ik deze ronde overleef, maarja het is een leuke uitdaging!

[Ghost(NL)]

@The Flying Dutchman:

Ja, dat is zo'n beetje hetzelfde als wat ik beschrijf, ok, leuk!

[The Flying Dutchman]

Hmm... was begonnen met Squished Status, maar mijn huidige oplossing doet er veel te lang over (hij is ondertussen al een paar minuten bezig met een input van 1000 characters). Zal mijn aanpak iets moeten wijzigen (weet al ongeveer hoe, wel jammer van de verloren tijd).

[MrHaas]

The Flying Dutchman schreef op zaterdag 28 januari 2012 @ 20:52:
Hmm... was begonnen met Squished Status, maar mijn huidige oplossing doet er veel te lang over (hij is ondertussen al een paar minuten bezig met een input van 1000 characters). Zal mijn aanpak iets moeten wijzigen (weet al ongeveer hoe, wel jammer van de verloren tijd).

Ik heb m net gesubmit, hij deed er 0.004999s in python

[Soultaker]

Zolang je er maar achter komt vóór je de officiële testinvoer downloadt hè. (Serieus, lokaal testen op problematische invoer is een goed idee!)

edit: Ik ben klaar trouwens.

[ Voor 11% gewijzigd door Soultaker op 28-01-2012 20:54 ]

[The Flying Dutchman]

MrHaas schreef op zaterdag 28 januari 2012 @ 20:53:
[...]


Ik heb m net gesubmit, hij deed er 0.004999s in python

Ja, mijn aanpak was een beetje naïef. Even aanpassen en dan zou het heel wat sneller moeten kunnen .

Soultaker schreef op zaterdag 28 januari 2012 @ 20:53:
Zolang je er maar achter komt vóór je de officiële testinvoer downloadt hè. (Serieus, lokaal testen op problematische invoer is een goed idee!)

Inderdaad, daarom getest op een zelfgegenereerde input van 1000 chars.

edit: Ik ben klaar trouwens.

Toch niet met alledrie??

[Soultaker]

Jawel, anders zat ik nu niet te GoT'en.

[MrHaas]

Soultaker schreef op zaterdag 28 januari 2012 @ 20:59:
Jawel, anders zat ik nu niet te GoT'en.

Wow, respect! (mits ze alle 3 goed zijn uiteraard )

[The Flying Dutchman]

MrHaas schreef op zaterdag 28 januari 2012 @ 21:00:
[...]


Wow, respect! (mits ze alle 3 goed zijn uiteraard )

Inderdaad respect!
*gaat snel weer even verder*

[pientertje]

Oeh. Ik ga nu beginnen.

[The Flying Dutchman]

Goed... ondertussen squished ingeleverd. Hopelijk was het goed... *fingers crossed*.
Even kijken welke ik nu ga doen...

[creator1988]

Volgens mij begrijp ik die Checkpoint opdracht niet. Bij het voorbeeld geven ze bij 5 het antwoord 6 aan. Maar met een checkpoint op 1,1 en een finish op 2,3 heb je ook 5 stappen (2 + 3) maar met oplossing 5? Wat mis ik?

[Soultaker]

In jouw voorbeeld heb je 5 stappen, maar zes verschillende routes. Twee paden om van (0,0) naar (1,1) te komen, en 3 paden om van (1,1) naar (2,3) te komen geeft in totaal 6 paden (2×3, niet 2+3).

[creator1988]

Ah figures, thanks. Moet geen code proberen te schrijven op zaterdagavonden :-)

[pientertje]

Jammer, ik heb de eerste opdracht verprutst. Ik kan niet helder genoeg denken Morgen maar proberen of ik die andere twee nog kan.

[Jegorex]

Squished Status heeft best wel grote getallen...
Voordat ik de modulo eroverheen gooi zijn er meerdere Java Long antwoorden negatief omdat het groter is dan Long.MAX_VALUE

Verder ben ik nooit verder gekomen dan middelbare school wiskunde, dus heb ik mijn eigen "formule" in elkaar geknutseld die hopelijk doet wat hij moet doen.

[Soultaker]

Het helpt waarschijnlijk om te weten dat (a + b)%c = (a%c + b%c)%c (en dat geldt behalve voor optellen, ook voor aftrekken, vermenigvuldigen en machtsverheffen; alleen delen is ingewikkelder!)

[Wolfboy]

Doh... net naar de opdrachten gekeken. Meer wiskunde dan programmeerproblemen helaas... weinig zin in op het moment. Misschien morgenmiddag maar eens kijken

[MrHaas]

Heb ze ook eindelijk allemaal gesubmit. Vermoed dat ik ze wel goed heb...

[Jegorex]

Soultaker schreef op zondag 29 januari 2012 @ 01:59:
Het helpt waarschijnlijk om te weten dat (a + b)%c = (a%c + b%c)%c (en dat geldt behalve voor optellen, ook voor aftrekken, vermenigvuldigen en machtsverheffen; alleen delen is ingewikkelder!)

Ik heb mijn code aangepast en sommige antwoorden zijn nu anders.
Misschien dat ik morgen nog een andere opdracht doe en anders zie ik volgend jaar wel weer.

[MrHaas]

Soultaker schreef op zaterdag 28 januari 2012 @ 18:02:
@MrHaas: nette code, maar wat is de tijdcomplexiteit van die oplossing?

Op de officiële testdata heeft 'ie hier 3 uur (!) nodig (met uitschieters van een half uur per testcase) weliswaar met CPython 2.6.2 maar op een behoorlijk snel systeem. Ik zie dus niet hoe jij op 4 minuten uitkomt... of ik doe iets verkeerd, of jij.

Interessant, als ik 'm op Python 2.6 draai, doet ie er bij mij ook heel lang over op zelfde systeem. Eens kijken waar hij tijd verliest tov 2.7.

/edit: ha, gevonden, bug in oude python-versies mbt garbacecollection: http://bugs.python.org/issue4074. Als je gc disabled runt ie m ongeveer net zo snel als 2.7

[ Voor 12% gewijzigd door MrHaas op 29-01-2012 14:04 ]

[The Flying Dutchman]

Zojuist ook recover the sequence ingeleverd... had niet getest op hele grote data (omdat ik er vertrouwen in had dat mijn algoritme efficient was) en kneep hem een halve seconde toen mijn programma niet direct output genereerde. Gelukkig was het vals alarm.

Execution time: 0m1.261s

Achteraf gezien had ik nog een kleine optimalisatie ergens kunnen uitvoeren in de laatste stap van mijn algoritme, maar aangezien N maximaal 10000 deed dat er eigenlijk niet zoveel toe.

Eens even kijken of ik checkpoint nog kan inleveren... heb al ontzettend lang over die opdracht na zitten denken maar ben er nog niet helemaal uit hoe ik het op een efficiente manier moet oplossen.

edit:
Ook checkpoint ingeleverd. Heb gisteren veel te lang nagedacht over een veel te mooie oplossing. Zou met wat betere boekhouding nog wel iets sneller kunnen. Of er echt een mooie oplossing is weet ik zo eigenlijk niet. Eerst getest met een input file met 20 problemen met S > 10000000 (en een S die gekozen was om mijn code zo zwaar mogelijk te belasten). Die deed er op mijn quad core bijna een minuut over.

Uiteindelijke officiele input ging in 0m4.193s

[ Voor 26% gewijzigd door The Flying Dutchman op 29-01-2012 15:55 ]

[Soultaker]

MrHaas schreef op zondag 29 januari 2012 @ 13:19:
/edit: ha, gevonden, bug in oude python-versies mbt garbacecollection: http://bugs.python.org/issue4074. Als je gc disabled runt ie m ongeveer net zo snel als 2.7

Aha! Dat was 'm inderdaad.

Kun je je algoritme ook nog toelichten?

[Soultaker]

En de tijd is op! Veel mensen met alledrie de opgaven ingezonden, hoewel het nog de vraag is of ze ook allemaal goed zijn natuurlijk.

Ik heb weer een weblog post gemaakt met een analyse van de problemen.

[MrHaas]

Soultaker schreef op zondag 29 januari 2012 @ 16:31:
[...]

Aha! Dat was 'm inderdaad.

Kun je je algoritme ook nog toelichten?

Ik doe m'n best, ben niet zo heel goed in uitleggen ;):

• Initialisatie:
• Bereken de P's en W's tot er herhaling optreedt en bewaar herhalende (tail) en niet-herhalende (head) deel apart. Bewaar ook de lookup-dictionaries voor P en W waarbij de key de waarde van P of W is en de value de index in p_head + p_tail (of w_head + w_tail in geval van w)
• Maak een kopie van de totale lijst P's (herhalend + niet-herhalend) en van de W's en sorteer deze.
• Maak van de gesorteerde lijsten ook nog een dictionary met als key de waarde van P of W en als value de index in de gesorteerde lijst.
  
  Berekenen van Bargains en Terribles:
• Definieer min_p, max_p, min_w, max_w als de posities van de minimale en maximale p en w in de gesorteerde lijst van P en W, initieel dus min_p = min_w = 0 en max_p = len(P) - 1, max_w = len(W) - 1.
• Loop zolang max_p >= min_p en max_w >= min_w
• Bepaal welke range het kleinst is (max_w in min_w) of (max_p in min_p)
• Als de kleinste range P is, ga dan van de minimale p (sorted_p[min_p]) alle beschikbare w's zoeken, dwz alle w's waarmee p een product vormt rekening houdend met de gegeven N. Dit doe je door de eerste p op te zoeken in de de ongesorteerde lookup-dict.
  Als die positie binnen de head ligt, dus in het niet-herhalende deel, is er maar 1 combinatie (p,w) beschikbaar en die kan je makkelijk opzoeken. In het andere geval ga je door de periode heen lopen van de productcombinaties (De periode is de lcm van len(p_tail) en len(w_tail).) met stappen van len(p_head) en voor die posities zoek je de bijbehorende w.
  Zo heb je een lijst van w's die combineren met p en daarvan neem je de kleinste (aangezien dat per definitie de enige is die eventueel bargain is). Van die combinatie (p, w) kan je direct berekenen hoe vaak die voorkomt aan de hand van N/period waarbij N het aantal producten is.
  Je hebt nu de kleinste w behorend bij min_p. Als w binnen de range min_w-max_w ligt, dan betekent het dat we een nieuwe bargain hebben gevonden. De max_w schuift dan op naar de gevonden w - 1. In elk geval schuift de min_p 1 postie verder richting de max_p.
• Voor de terribles geldt ongeveer hetzelfde alleen beginnen we daar vanaf max_p en max_w en kijken we naar de grootste gevonden p of w.

Hoop dat 't beetje duidelijk is .

[MrHaas]

Soultaker schreef op zondag 29 januari 2012 @ 19:28:
En de tijd is op! Veel mensen met alledrie de opgaven ingezonden, hoewel het nog de vraag is of ze ook allemaal goed zijn natuurlijk.

Ik heb weer een weblog post gemaakt met een analyse van de problemen.

Ik ben benieuwd. Ze vielen best mee he deze ronde?

[The Flying Dutchman]

Ronde 1 is ondertussen afgelopen. Tel ik nu slechts 3 Gotters die alledrie de opdrachten ingeleverd hebben? Hieronder de algmene aanpak voor de 3 problemen die ik heb gevolgd:

1. Checkpoint:

• Ontbind S in alle mogelijke factoren. Heb dit gewoon met een for loopje gedaan dat van 1 t/m ceil(sqrt(S)) itereerd om te kijken welke delingen een rest van 0 opleveren. Met een S <= 10000000 was dit goed te doen.
• Nu weet je welke factoren samen S opleveren, dit is belangrijk omdat er m mogelijke routes van 0,0 tot checkpoint zijn en n mogelijke routes van checkpoint tot finish. In totaal levert dat m x n = S mogelijke routes.
• Doorzoek de 2d grid op alle mogelijke factoren die je gevonden hebt. De grid kan opgebouwd worden door linker en onderkant te initialiseren met de waarden 1 (immers: er is slechts 1 manier om bij de onderkant of zijkant langs te lopen). Vervolgens is het aantal mogelijke manieren om op (x,y) te komen gelijk aan de som van de mogelijke manieren om op (x-1, y) en op (x, y - 1) te komen. Visueel:
  
  code:
  

  5   1   6  21  56 126 252
  4   1   5  15  35  70 126
  3   1   4  10  20  35  56
  2   1   3   6  10  15  21
  1   1   2   3   4   5   6
  0   0   1   1   1   1   1
  
      0   1   2   3   4   5

• Het is niet nodig om de hele grid te doorzoeken: je kunt bij de eerste rij (of kolom) beginnen en stoppen met de rij zodra het aantal combinaties om op het punt te komen groter is dan S. Dit gaat steeds sneller naarmate je verder van de rand van het veld afraakt. Ook hoef je niet bij iedere rij aan het begin te beginnen maar kun je op rij K op index K beginnen (wat daarvoor komt heb je immers al in rijen 0 - K-1 gezien).
• Onthoudt bij het doorzoeken van de grid de kortste weg om bij iedere mogelijke factor van S te komen. In bovenstaande grid zie je bijvoorbeeld dat het mogelijk is om 4 stappen bij factor 6 te komen (2 naar rechts, 2 omhoog) maar ook in 6 stappen (5 naar rechts, 1 omhoog).
• Bereken voor iedere combinatie van factoren die samen S opleveren wat de afstand is: de kleinste afstand is het antwoord.

2 Recover the Sequence:

• Het eind resultaat van een merge-sort op een lijst van 1 ... N is natuurlijk de gesorteerde lijst van 1 ... N. Ik heb eerst deze lijst aangemaakt.
• Op deze lijst heb ik vervolgens merge sort losgelaten met een kleine aanpassing: het sorteren gebeurt niet op basis van de waarden in de lijst maar op basis van de debug output.
• Dit resulteerd in een lijst met nummers van 1 ... N, maar dit is nog niet de oorspronkelijke lijst.
• De oorspronkelijke lijst kan teruggevonden worden door voor de getallen 1 ... N te kijken op welke index in de lijst ze staan. Een voorbeeld: [ 4 1 3 2 ] levert op [ 2 4 3 1 ]. Dit is de oorsponkelijke lijst (de waarde 1 staat op index 2, de waarde 2 staat op index 4, etc).

3. Squished status:

• Ik heb eerst de input string geconverteerd naar een lijst single digit getallen.
• Vervolgens de lijst van achter naar voor doorgelopen (had waarschijnlijk net zo goed andersom gekunt... maar vooruit).
• Voor 1 ... N met N de lengte van de lijst:
  • Neem de waarde op index i.
  • Als dit niet 0 is (is namelijk ongeldig), verhoog dan het aantal mogelijke oplossingen op index i met de som van gevonden mogelijke oplossingen op index i+1.
  • Vermenigvuldig de waarde met 10 en tel er de waarde uit de lijst van i+1 bij op.
  • Als dit een geldige waarde oplevert (kleiner dan grootst mogelijke character), verhoog het aantal mogelijke antwoorden met de som van gevonden mogelijke oplossingen op index i+2.
  • Vermenigvuldig weer met 10, en herhaal bovenstaande stappen tot de waarde groter is dan het grootst mogelijke character.
• Sla het totaal van mogelijke antwoorden (modulo 0xfaceb00c) die gevonden zijn voor index i op in een lijst en ga door met index i - 1.
• Blijf herhalen tot je bij index 0 bent. Nu heb je het antwoord.

Al met al vond ik Checkpoint het lastigste. Ik heb erg lang zitten nadenken over een formule om te bepalen op hoeveel mogelijke manieren je op (m, n) kunt komen. Als m == n dan is dat niet zo lastig (daar is een formule voor). Maar ik kon er niet uitkomen bij m != n. Uiteindelijk gewoon de grid doorgelopen en dat bleek veel minder cpu tijd te kosten dan ik in eerste instantie dacht.

Ik had na de kwalificatie een framework opgezet dat met meerdere threads tegelijk problemen kan oplossen en voor ieder probleem een nieuwe problem solver instance aanmaakt. Daardoor moest ik bij Checkpoint voor ieder probleem opnieuw de grid genereren. Dat was de grootste inefficientie in mijn algoritme.

Bij Sequence had ik een iets handigere data structuur kunnen gebruiken om aan het einde de vertaalslag te maken (vinden van posities van 1 ... N in de lijst). Ik heb gewoon voor 1 ... N de lijst doorgezocht, maar met een handige data structuur had ik natuurlijk gewoon een sorteer actie kunnen doen.

[MrHaas]

The Flying Dutchman schreef op zondag 29 januari 2012 @ 19:47:
Ronde 1 is ondertussen afgelopen...

Grappig, je aanpak lijkt heel erg op de mijne, ook dat frameworkje met meerdere threads .
Mergesort heb ik exact zelfde manier en Checkpoint komt ook heel erg in de buurt. Vond ook Checkpoint de lastigste.

[Soultaker]

[quote]The Flying Dutchman schreef op zondag 29 januari 2012 @ 19:47:
• Doorzoek de 2d grid op alle mogelijke factoren die je gevonden hebt. De grid kan opgebouwd worden door linker en onderkant te initialiseren met de waarden 1 (immers: er is slechts 1 manier om bij de onderkant of zijkant langs te lopen). Vervolgens is het aantal mogelijke manieren om op (x,y) te komen gelijk aan de som van de mogelijke manieren om op (x-1, y) en op (x, y - 1) te komen.
Oh grappig, dit is eigenlijk veel directer beredeneerd dan ik deed. En als je je jouw grid 135 graden draait kom je ook op de driehoek van Pascal uit.

Al met al vond ik Checkpoint het lastigste. Ik heb erg lang zitten nadenken over een formule om te bepalen op hoeveel mogelijke manieren je op (m, n) kunt komen. Als m == n dan is dat niet zo lastig (daar is een formule voor). Maar ik kon er niet uitkomen bij m != n.

Dat zijn dus die binomiaalcoëfficiënten; C(a,b) is het aantal combinaties van b uit a waarbij je C(n+m,n) (of C(n+m,m), wat hetzelfde is) wil uitrekenen. Op de middelbare school leer je dat C(a,b)=a!/b!/(a-b)! maar vaak is C(a,b) = C(a-1,b-1)+C(a-1,b) handiger (en dat is ook de recurrente betrekking waar de driehoek van Pascal op gebaseerd is).

(Ik neem aan dat je ooit kansrekening gehad hebt? Zoniet, dan dubbel respect dat je het probleem puur op eigen inzicht opgelost hebt!)

[ Voor 44% gewijzigd door Soultaker op 29-01-2012 20:41 ]

[- peter -]

Nou, ik moest helaas afhaken vanwege het niveau. Kon bij alledrie de vraagstukken maar niet bedenken hoe ik het op kon lossen. Wel een beetje geprutst, maar helaas.

[Soultaker]

@MrHaas: bedankt voor je uitleg! Het deel waar ik vooral moeite mee had is niet zozeer dat je oplossing werkt (de aanpak is duidelijk correct) maar dat 'ie snel genoeg is in alle mogelijke gevallen.

De truc lijkt 'm erin te zitten dat je de ruimte waarin mogelijke bargains zitten steeds nauwkeuriger afschat, en op die manier afdwingt dat je daar ofwel een klein aantal iteraties voor nodig hebt, óf dat het aantal gevonden producten/gewichten per iteratie klein is. Het lijkt erop dat je oplossing dus O(N+M) tijd nodig heeft, hoewel ik niet direct een exact bewijs daarvoor kan geven.

In ieder geval vind ik 'm erg mooi gevonden; ik had dit zelf nooit zo bedacht, dus bedankt dat je 'm postte!

---

Fuuuuuuuuuuu! Ik kom er net achter dat ik in m'n oplossing voor Squished Status een i heb staan die een j had moeten zijn. Die ga ik dus sowieso falen. Nu maar hopen dat een stuk of 1000 anderen óók (minstens) een probleem falen.

[ Voor 17% gewijzigd door Soultaker op 29-01-2012 23:12 ]

[The Flying Dutchman]

Soultaker schreef op zondag 29 januari 2012 @ 20:24:
@MrHaas: bedankt voor je uitleg! Het deel waar ik vooral moeite mee had is niet zozeer dat je oplossing werkt (de aanpak is duidelijk correct) maar dat 'ie snel genoeg is in alle mogelijke gevallen.

De truc lijkt 'm erin te zitten dat je de ruimte waarin mogelijke bargains zitten steeds nauwkeuriger afschat, en op die manier afdwingt dat je daar ofwel een klein aantal iteraties voor nodig hebt, óf dat het aantal gevonden producten/gewichten per iteratie klein is. Het lijkt erop dat je oplossing dus O(N+M) tijd nodig heeft, hoewel ik niet direct een exact bewijs daarvoor kan geven.

In ieder geval vind ik 'm erg mooi gevonden; ik had dit zelf nooit zo bedacht, dus bedankt dat je 'm postte!

---

Fuuuuuuuuuuu! Ik kom er net achter dat ik in m'n oplossing voor Squished Status een i heb staan die een j had moeten zijn. Die ga ik dus sowieso falen. Nu maar hopen dat een stuk of 1000 anderen óók (minstens) een probleem falen.

Dat is balen! En ik moet je teleurstellen... de nummer 500 had alledrie opgaven goed. Op basis daarvan ben ik zelf ook door (plek 611 met alledrie opgaven goed). Penalty: 41:47:05. Helaas kan ik de volgende ronde waarschijnlijk niet meedoen omdat ik op dat moment een verjaardag aan het vieren ben en de ronde slechts 3 uurtjes duurt...

[Tharulerz]

The Flying Dutchman schreef op maandag 30 januari 2012 @ 09:18:
[...]


Dat is balen! En ik moet je teleurstellen... de nummer 500 had alledrie opgaven goed. Op basis daarvan ben ik zelf ook door (plek 611 met alledrie opgaven goed). Penalty: 41:47:05. Helaas kan ik de volgende ronde waarschijnlijk niet meedoen omdat ik op dat moment een verjaardag aan het vieren ben en de ronde slechts 3 uurtjes duurt...

Laat Soultaker op je account

Jammer dat je niet doorbent door een Typo soul...

[SaphuA]

Pff, geen idee of ik door was, maar de contest is nu dus gesloten? Jammer Erg onoverzichtelijke contest zeg. Geen enkele e-mail notificatie gehad oid.

Anywho, succes aan de mensen die er wel op tijd bij waren

[ Voor 17% gewijzigd door SaphuA op 30-01-2012 09:57 ]

[MrHaas]

Balen joh, ik ben op 249 geeindigd. Moet nog wel wat aan snelheid gaan werken wil ik beetje kans maken om ronde 3 te halen...

Mijn source:
checkpoint: http://pastebin.com/2yFvaHWz
recover the sequence: http://pastebin.com/kTPm3hNj
squished status: http://pastebin.com/5RDk67n5

[The Flying Dutchman]

MrHaas schreef op maandag 30 januari 2012 @ 09:58:
Balen joh, ik ben op 249 geeindigd. Moet nog wel wat aan snelheid gaan werken wil ik beetje kans maken om ronde 3 te halen...

Mijn source:
checkpoint: http://pastebin.com/2yFvaHWz
recover the sequence: http://pastebin.com/kTPm3hNj
squished status: http://pastebin.com/5RDk67n5

Als ik kon deelnemen aan ronde 2 dan had ik ook wat sneller moeten opleveren... ben zaterdagavond niet erg lang doorgegaan en heb zondag uitgeslapen. Maar ik was al bijna 3 uur bezig voordat ik zaterdagavond de eerste opdracht opgeleverd had (in totaal denk ik ongeveer 8-9 uur gedaan over de drie opdrachten bij elkaar).

[ Voor 5% gewijzigd door The Flying Dutchman op 30-01-2012 10:05 ]

[Soultaker]

Tharulerz schreef op maandag 30 januari 2012 @ 09:19:
Jammer dat je niet doorbent door een Typo soul...

Ja, ik baal enorm. Vooral omdat 't zo'n lullige fout is in nota bene het makkelijkste probleem. Maar ja, ik heb die code zelf getypt, dus eigen schuld, dikke bult. Volgend jaar beter.

Lijkt erop dat MrHaas zo'n beetje de enige Tweaker is die nog wél in de running is én tijd heeft om mee te doen komend weekend? Ik zal zaterdag voor hem duimen dan.

[_Moe_]

Zijn de opdrachten zelf hier eigenlijk ergens beschikbaar? Zou ze misschien ook wel eens willen proberen.

[Soultaker]

Als je een Facebook account hebt kun je ze hier zien, als het goed is. Ik heb ze ook hier gelinkt maar dan moet je even langs de spoilers heen lezen.

[MrHaas]

ik heb zaterdag tijd, dus ga sowieso een poging wagen. Intussen beetje aan het oefenen met Google Codejam puzzels.

[genesisfm]

Respect voor jullie! Ik rommel zo nu en dan wat in software (vb :x) maar als ik jullie zo hoor praten dan heb ik het idee dat ik iets heb gemist op school :x

[- peter -]

Ben benieuwd of er nog iemand naar de 3e ronde is gekomen? MrHaas?

[The Flying Dutchman]

De 2e ronde begint vanavond om 22.00u NL tijd. Mijn plannen zijn gewijzigd en nu kan ik toch meedoen. Ik verwacht niet dat ik ver kom: de ronde duurt slechts 3 uur en ik zal aanzienlijk sneller mijn opdrachten moeten inleveren dan de vorige keer om verder te komen. We zullen zien.

[MrHaas]

We gaan beginnen. Beetje grieperig vandaag, dus ben benieuwd of het wat wordt...

GL

/edit: en al weer gestopt, kan niet helder denken met koppijn.

[ Voor 27% gewijzigd door MrHaas op 04-02-2012 22:58 ]

[The Flying Dutchman]

Ik heb zojuist Monopoly ingeleverd... hij deed het goed op de testset, maar niet heel goed doorgedacht... dus durf niet te zeggen of de oplossing correct was.

Kijken of ik nog een oplossing kan inleveren...

edit: scores zijn bekend, voor mij is het afgelopen (niet geheel onverwacht). De enige oplossing die ik ingeleverd had bleek ook nog eens fout te zijn. Ik was al wel een eindje met een tweede oplossing, maar die kreeg ik niet op tijd af.

Was wel een leuke competitie.

[ Voor 40% gewijzigd door The Flying Dutchman op 05-02-2012 09:24 ]

[Soultaker]

Allebei afgevallen? Jammer.

[Ghehe]

Datums van de hacker cup zijn bekend (net op fb zien voorbij komen):

Attention Hackers! The dates have been set for Facebook Hacker Cup 2013.

Jan 7 - Jan 27-- Registration
Jan 25 - Jan 27 -- Online Qualification Round
Feb 2 -- Online Elimination Round 1
Feb 9 -- Online Elimination Round 2
Feb 16 -- Online Elimination Round 3
March 22 -23 -- Onsite Finals at Facebook

Registration will open next week - stay tuned!

Valt voor mij net mooi. 25 Januari mijn laatste examen en heb dan tot 10 Februari vakantie. Dit jaar eens mijn best doen en kijken hoever ik geraak.

[P-Storm]

Niet om lullig te doen, maar is het niet beter dat een nieuwe topic voor deze reeks aangemaakt wordt? Verder wel fijn voor de data

[azerty]

Ghehe schreef op zaterdag 05 januari 2013 @ 01:02:
Datums van de hacker cup zijn bekend (net op fb zien voorbij komen):


[...]


Valt voor mij net mooi. 25 Januari mijn laatste examen en heb dan tot 10 Februari vakantie. Dit jaar eens mijn best doen en kijken hoever ik geraak.

Van mij blijft er 1 of 2 over, dus ik kan wel een gokje wagen

[Ghehe]

P-Storm schreef op zaterdag 05 januari 2013 @ 01:04:
Niet om lullig te doen, maar is het niet beter dat een nieuwe topic voor deze reeks aangemaakt wordt? Verder wel fijn voor de data

Facebook Hacker Cup 2013 Voila se.

[Verwijderd]

Heren,
Ik heb nu ongeveer 50 progammatjes gedownload om een facebook te hacken waarvan ik het e-mailadres wel heb. Nu kwam ik toevallig op dit forum ,mijn vraag is is het echt te doen of is het niet te doen.
Ook al enkele mensen gemaild die het zouden kunnen maar ook niets!
Hoor het graag?!

Groet Ronnie

[BtM909]

Als je toegang wilt tot een Facebook-account, dan raad ik je aan om contact te nemen met Facebook's supportafdeling!