Facebook Hacker Cup

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

[Anoniem: 545369]

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!