Facebook Hacker Cup 2013

[Ghehe]

Facebook Hacker Cup 2013

Wat is de Facebook Hacker Cup?

De Facebook Hacker Cup is een jaarlijkse programmeerwedstrijd waarin hackers (efficiënte) oplossingen proberen te bedenken voor bepaalde problemen.

De Facebook Hacker Cup bestaat sinds 2011 en is Facebooks officiële programmeerwedstrijd.

Wanneer is de Facebook Hacker Cup?

De dagen waarop de competitie doorgaan, zijn sinds gisteren (4 januari 2013) bekend:
Jan 7 - Jan 27-- Registratie
Jan 25 - Jan 27 -- Online kwalificatieronde
Feb 2 -- Online kwalificatieronde 1
Feb 9 -- Online kwalificatieronde 2
Feb 16 -- Online kwalificatieronde 3
March 22 -23 -- Finale @ Facebook Headquarters

Hoe kan ik meedoen

Simpel, als je al een facebook account hebt, kan je met dat account je inschrijven voor de Hacker Cup. Inschrijven doe je op https://www.facebook.com/hackercup/register.

Vragen

Het concept is simpel, je krijgt een probleem en daar moet jij een oplossing voor vinden. Je krijgt bij je probleem al een hele simpel voorbeeld van input en output. Als jij denkt dat je oplossing het probleem kan oplossen dan download je wedstrijd-inputdata en haal je die door je programma. De ouput upload je naar Facebook welke je oplossing zal nakijken en als juist of fout zal beoordelen.

Vragen kwalificatieronde 2012
Vragen Finale 2011 (beetje scrollen)

Van andere competities:
NWERC 2012 (Vragen/Oplossingen)
BAPC 2012 (Vragen/Oplossingen/Testdata) (Zip-bestand)
Vlaamse Programmeerwedstrijd '09, '10, '11, '12 (Vragen/Oplossingen/Testdata)

Hackers Wall of Fame

Soultaker - Finale 2011 (laatste 25)

Voorgaande topics

In de voorgaande topics kan je vragen, oplossingen en discussies terugvinden.
HC 2011
HC 2012

[ Voor 5% gewijzigd door Ghehe op 10-01-2013 23:28 ]

[Anoniem: 170251]

Cool, ga ik me ook maar inschrijven. Kijken of ik door de eerste ronde heen ga komen

[Anoniem: 170251]

Thank you for registering. Please check the Hacker Cup page for updates on the Hacker Cup.

Done!

De link voor registratie is trouwens: http://www.facebook.com/hackercup/register

[ Voor 29% gewijzigd door Anoniem: 170251 op 07-01-2013 09:16 ]

[kokx]

Anoniem: 170251 schreef op maandag 07 januari 2013 @ 09:15:
De link voor registratie is trouwens: http://www.facebook.com/hackercup/register

Het lijkt erop dat die nog van 2012 is. Waarschijnlijk moeten we nog even wachten todat ze op http://www.facebook.com/hackercup met de registratie URL komen.

[Jegorex]

Registratie is nu geopend: http://www.facebook.com/hackercup/posts/445489108850072

[HuHu]

Ik heb me ingeschreven, ben benieuwd

[Anoniem: 170251]

Het was dus toch de goede link, alleen was gisteren de banner nog niet bijgewerkt Want ik sta zo te zien wel gewoon ingeschreven.

[kokx]

Anoniem: 170251 schreef op dinsdag 08 januari 2013 @ 08:54:
Het was dus toch de goede link, alleen was gisteren de banner nog niet bijgewerkt Want ik sta zo te zien wel gewoon ingeschreven.

Ja, ze hebben iedereen die zich voor vorig jaar had ingeschreven, ook automatisch laten inschrijven voor 2013.

[sub0kelvin]

Ik heb me ook maar geregistreerd dit keer. Ik heb de komende tijd "niks" te doen (zit in Canada en heb nog geen werkvergunning) dus heb tijd genoeg om hier serieus aandacht aan te geven. Bij de Google Code Challenge van 2012 had ik geen tijd om meer dan de kwalificatieronde te doen en dat vond ik wel wat jammer.

Mijn tools of the trade zullen voornamelijk Java en wat Python zijn, afhankelijk van het probleem.

[drm]

Juicyhil:
Het was dus toch de goede link, alleen was gisteren de banner nog niet bijgewerkt Want ik sta zo te zien wel gewoon ingeschreven.

http://martinfowler.com/bliki/TwoHardThings.html

[- peter -]

Wat wel het belangrijkste is van wat ik vorig jaar geleerd heb, is dat bruteforce oplossingen absoluut niet je verder helpen. Je moet echt een slim algoritme bedenken, omdat de voorbeeld opgaven bijvoorbeeld waardes hadden van 0 - 20, en de echte input die je in 5 minuten moest processen bijv van 0 - 1.000.000.

Daar ging ik aardig mee over de kop. Ik kom als Android programmeur best mee in het dagelijks leven, maar hier is wel veel algoritmische kennis vereist (in de latere rondes). Maar desondanks heel leuk om te doen!

[Cypher87]

Heb me ook maar ingeschreven :-)

[Anoniem: 430662]

Tof! Vorig jaar tot in de tweede ronde geraakt, dan geen tijd meer helaas. Heb vroeger nog wat Project Euler problemen opgelost maar dat is meer wiskunde gericht. Veel succes!

Welke programmeertalen gebruiken jullie? Ik neig nogal rap Ruby te gebruiken voor zo'n problemen maar dat is niet echt het meest performante.

[Anoniem: 304426]

Dit klinkt ook wel als iets wat in mn straatje past
Net als hierboven heb ik e.e.a. aan project euler gedaan maar eerlijk is eerlijk: dat ging me niet altijd makkelijk af. Ik ben benieuwd hoe ver ik kom.

@ boven:
Zelf doorgaans visual basic en meer recent python.

EDIT:
Geven jullie je echte adresgegevens op? I.v.m. dat t-shirt. Ondergetekende is gierig en zou 't op zich wel willen.

[ Voor 31% gewijzigd door Anoniem: 304426 op 09-01-2013 19:21 ]

[Anoniem: 430662]

@boven: Vorig jaar kon je op elk moment je adres gegevens veranderen, dus stel dat je tot de tshirt ronde raakt kun je dan je echte adres invullen normaal.

Met project euler blijf ik ook steken vanaf probleem 60-100. Maar dat is vooral omdat mijn wiskunde kennis niet zo ver rijkt. Bij de Hacker Cup zijn het meer logische problemen.

[Eärendil]

Ik heb me dit jaar ook weer inschreven. Vorig jaar met 2 van de 3 problemen goed door de qualification round gekomen, maar daarna gefaald in round 1

[Soultaker]

Dit is wel een aardig opwarmertje voor volgende week: Colossal Cue Adventure.

[Beatboxx]

Jullie doen neem ik aan het meeste in Python? Hoe ver zou je komen, met alleen kennis van Python?

[Soultaker]

Ik gebruik zelf waarschijnlijk Python voor de voorronde on C++ voor de rest van de wedstrijd. Op zich moet je met Python alleen heel ver kunnen komen, maar ik vermoed dat de beste deelnemers de meeste problemen gewoon in een traditionale taal als C++, C# of Java zullen oplossen.

Ik denk dat je met kennis van Python en een flinke dosis wiskundig inzicht sowieso veel verder komt dan dat je 10 jaar ervaring met C++ hebt maar geen probleemoplossend vermogen.

[tha_crazy]

Ik ga deze even bijhouden.
Misschien is het wel leuk om mijn programmeerkennis te testen.

Vanavond maar eens goed naar kijken

[Beatboxx]

Mja, maar mijn kennis van Python is vrij behelpen Ik ga nog even een jaartje door-oefenen, ik zie jullie over een jaartje!

[HuHu]

Python is niet verplicht hè, je mag elke taal gebruiken die je wilt.

[Beatboxx]

Denk niet dat ik met HTML&CSS heel erg ver kom..... Verder kan ik ook een basisje PHP, maar dat lijkt me nu niet de meest geschikte taal.

[HuHu]

PHP moet ook lukken. Kijk maar naar de oplossing van Alphabet Soup van vorig jaar. Dat is ook eenvoudig in PHP te doen.

[Anoniem: 485772]

Oooh nice, ty OP

Ik ga mogelijk iets doen in C#, C++ of zelfs PHP

[tha_crazy]

Anoniem: 485772 schreef op dinsdag 22 januari 2013 @ 10:11:
Oooh nice, ty OP

Ik ga mogelijk iets doen in C#, C++ of zelfs PHP

Als ik meedoe doe ik dat in C#.
Toch de taal waar ik dagelijks in werk

[Anoniem: 485772]

Soultaker schreef op zondag 20 januari 2013 @ 18:00:
Dit is wel een aardig opwarmertje voor volgende week: Colossal Cue Adventure.

Nice one, nu vraag twee nog

code:

> talk rabbit

The rabbit looks up from reading JIRA tickets, saying, "Hi, I'm Bugs", in what
we promise is the worst pun in the game, with the possible exception of the
very next line.

"I'm pulling my hare out trying to track down this bug.  Can you take a look at
this?"

He shows you the screen, which is displaying:

{]

1

({})}()

4

{{[{{{{}}{{}}}[]}[][{}][({[((
{{[][()()]}}{[{{{}}}]}))][()]
{[[{((()))({}(())[][])}][]()]
}{()[()]}]})][]]}{{}[]}}

"Apparently folks, at some point, that third string goes wrong too.  When you
find out what index has an incorrect closing mark, type it in to the
computer."

"As you can see I solved the first two problems, but I just can't crack the
third one."

Edit:

code:

> look computer

The computer is a MacBook Pro attached to a 27 inch Cinema Display and Kinesis
keyboard.</shamelessplugforyourdevsetupatcue>

[ Voor 8% gewijzigd door Anoniem: 485772 op 22-01-2013 10:25 ]

[SaphuA]

.

[ Voor 163% gewijzigd door SaphuA op 31-01-2022 15:07 ]

[Anoniem: 485772]

Hint

spoiler:

Wikipedia: Linear congruential generator

[Soultaker]

@SaphuA: je denkt sowieso veel te moeilijk. Je hoeft bij die eerste opgave niets te bruteforcen, maar je zit een beetje op het verkeerde spoor bij het uitrekenen van de RNG. De pagina die tinus80 linkte is wel nuttig.

En dit zijn VAXes, maar aan die informatie heb je verder niets, behalve dat het feit dat de VAX een 32-bits ISA had verklaart waarom die RNG ook modulo 2³² berekend wordt, misschien.

[SaphuA]

.

[ Voor 177% gewijzigd door SaphuA op 31-01-2022 15:07 ]

[Anoniem: 485772]

Ja de 2e opgaaf is wat lastiger maar heb me er ook nog niet echt mee bezig gehouden

[Anoniem: 485772]

Let op, antwoorden in spoilers

spoiler:

96

code:

The computer beings loudly number crunching...

...

Level 2 Completed!

The screen changes and now reads:

8 8 4 4 ^
4 9 6 4 8
8 6 4 1 2
4 8 2 6 3
* 6 8 8 4

* you are here

Edit:

spoiler:

n (31)
e (23)
e (21)
n (17)
e (16)
e (14)
w (13)
n (9)
n (5)
e (win)

code:

It's a long walk...

You arrive at Joe's ^ Shack, hand your last 5 chips to Joe, who hands a ^
to Bugs.  Bugs eats the ^ and says:

"Thanks for the ^.  You did it!"

You have completed the Colossal Cue Adventure!

Drop us a line at

[e-mail]
Let us know what you thought, which Easter eggs you found, and if you're so
inclined, attach your resume and the code you used to get through the adventure.

or...

...

you can try your hand at the bonus level by typing bonus...

code:

> bonus

You blink.  When you open your eyes, you are surprised to find yourself back at
the roulette table.

The man says: "Welcome back.  Let's play again."

He points at the board, which displays the most recent results:
34, 27, 16, 1, 34, 31, 24, 17, 34, 35, 16, 13.

"You may have to try a few more things this time to reproduce these results."

"And this time, you'll need to bet correctly 3 times in a row."

He hands you a chip.

[ Voor 86% gewijzigd door Anoniem: 485772 op 22-01-2013 17:35 ]

[Soultaker]

Er is nog een bonus level hè.

[Anoniem: 170251]

48 minuten!

https://www.facebook.com/...php?round=185564241586420

[Woy]

Damn bij de laatste heb ik een foutje gemaakt, waardoor ik niet binnen de tijd was

[Woy]

Heeft het nog nut om nog een goede oplossing op te sturen, of krijg je sowieso geen punten als je buiten de tijd was?

[Anoniem: 170251]

Woy schreef op zaterdag 26 januari 2013 @ 12:03:
Heeft het nog nut om nog een goede oplossing op te sturen, of krijg je sowieso geen punten als je buiten de tijd was?

If you accidentally submit the wrong files or you realize that there is a problem with your program, you can resubmit as many times as you need to during the 6 minutes. Once the 6 minutes has ended, you may not submit again for that problem. The last submission within the 6 minutes will be used for grading.

Helaas!
Misschien een andere opdracht alsnog goed insturen?

[Woy]

De andere opdrachten had ik al correct ingestuurd.

[Pizzalucht]

Ik had per ongeluk de timer gestart bij het eerste probleem, dus ik maak sowieso niet echt kans.
Ga toch proberen de andere problemen correct in te sturen, 2 heb ik volgens mij goed gemaakt, op naar 3.

[Drak0z]

Ik maak sowieso geen kans meer op de hoofdprijs, maar toch begonnen
Mijn vraag is echter; maak ik een denkfout bij de 3e opdracht? Volgens mij matchen example inputs niet met example outputs...

[Soultaker]

Hoezo “geen kans”? Dit is alleen de kwalificatieronde hè; als je minstens één opgave goed hebt, mag je aan de eerste ronde meedoen, en voor het verdere verloop van de wedstrijd tellen resultaten behaald in eerdere ronden niet mee.

Het maakt dus helemaal niet uit hoe snel of hoeveel opgaven je dit weekeinde oplost, als je er maar één correct oplost.

[Drak0z]

Oh.. Dat scheelt Maar ik dacht dat het ook om de score ging met penalties voor tijd etc... Anyway, waar ik dus echt niet uit kom is waarom het antwoord bij de 3e opgave, case 1, 8 is. Daar maak ik gewoon simpelweg een denkfout.
Volgens mij kan het namelijk niet zo zijn dat de gezochte waarde n voor komt in de verzameling k (waarbij bij case 1 de m[16] = 8 ).

[Eärendil]

spoiler:

*previous* *k* values of m

[ Voor 80% gewijzigd door Eärendil op 26-01-2013 16:01 ]

[Drak0z]

Eärendil schreef op zaterdag 26 januari 2013 @ 15:58:
[...]

Dank! Ik snap hem

[wjvds]

Jammer, ik had de eerste 2 heel snel (en volgens mij correct ), derde was helaas wat moeilijker...mijn code werkte wel op het voorbeeld, maar ik had mijn code zo inefficient geschreven dat hij een long[n] nodig had in het memory...met n dus tot 10^9. Ik kwam er natuurlijk pas achter dat dat problemen zou geven (heap overflow) nadat ik de input had gedownload, en binnen 6 minuten was dat niet meer te fixen.

[Eärendil]

Om dat te voorkomen kan je zelf één of meerdere extra input voorbeelden maken met waardes die aan de grenzen liggen wat er mogelijk is in de input. Dan had je voordat die 6 minuten ingingen geweten dat je code te inefficiënt was.

[Soultaker]

Captain Hindsight

Wel goed advies, in principe. Nog beter is om over dit soort dingen na te denken vóór je begint te coden, anders riskeer je nog steeds dat je een hoop tijd verspilt met implementeren van een aanpak die uiteindelijk niet blijkt te werken.

Overigens lijkt het me wel zo sportief om discussies over de complexiteit van problemen en mogelijke valkuilen uit te stellen tot ná de kwalificatieronde.

[- peter -]

In probleem 3 noemen ze "*k*". Is dat een of andere notatie ergens voor, die sterretjes? Of is dat gewoon om de nadruk erop te leggen?

[ Voor 20% gewijzigd door - peter - op 26-01-2013 23:07 ]

[Soultaker]

Dat is puur om te benadrukken dat je alleen naar de voorgaande k elementen moet kijken, en dus niet naar álle andere elementen. (In dezelfde zin staan ook sterretjes om het woord “not” heen.)

[Woy]

Soultaker schreef op zaterdag 26 januari 2013 @ 17:06:
Captain Hindsight

Wel goed advies, in principe. Nog beter is om over dit soort dingen na te denken vóór je begint te coden, anders riskeer je nog steeds dat je een hoop tijd verspilt met implementeren van een aanpak die uiteindelijk niet blijkt te werken.

Overigens lijkt het me wel zo sportief om discussies over de complexiteit van problemen en mogelijke valkuilen uit te stellen tot ná de kwalificatieronde.

Hehe, ja inderdaad. Ik had er wel van te voren over nagedacht, maar blijkbaar niet genoeg. Door de eenvoud van de eerste twee opdrachten was ik denk ook een beetje overmoedig, en heb ik gewoon niet goed genoeg getest alvorens de input te downloaden.

[SaphuA]

.

[ Voor 101% gewijzigd door SaphuA op 31-01-2022 15:06 ]

[Soultaker]

Derde probleem: Find The Min. Je zoekt inderdaad het n-de element, maar dat is natuurlijk m[n - 1] als je arrays indexeert vanaf 0 (of er is iets heel anders mis).

[ Voor 47% gewijzigd door Soultaker op 28-01-2013 19:42 ]

[Elijan9]

Op de valreep toch maar meegedaan, blijft Firefox hangen in het uploaden van beautiful_strings

Andere twee in elk geval probleemloos geupload, al klopt de 3e vast niet (snap nog niet hoe ik bij de example output zou moeten komen), maar kon in elk geval testen of het uploaded bij Chromium geen kuren had. Mijn hoop is dus gevestigd op alleen de tweede opgave. Niet echt veelbelovend zo...

spoiler:

Bij 3 snap ik echt niet hoe je met n=97 en k=39 (dus een gat van 97-39 waardes na "k" gevuld met minuma tot dan toe als ik het goed lees) ooit zou kunnen uitkomen op 8. En geld niet sowieso dat het uiteindelijke resultaat tussen [n - 1 - k, n - 1] zou moeten liggen of heb ik de tekst echt zo verkeerd gelezen?

[ Voor 29% gewijzigd door Elijan9 op 28-01-2013 20:14 ]

[Ghehe]

De waarden in je array bereken je voor
0..k-1 met m[i] = (b * m[i - 1] + c) % r, 0 < i < k
k..n-1 met m[i] = mex(m[i-k]..m[i-1]), k <= i < n
(waarbij mex() dus het minimale getal teruggeeft dat er NIET inzit)

Dus bij n = 97 en k = 39 bereken je dus m[0]...m[38] met de eerste formule en vanaf m[39], neem je de mex (dus bij 39 is het mex(m[39-39]...m[38]), bij 40 mex(m[1]..m[39])).

[ Voor 13% gewijzigd door Ghehe op 28-01-2013 21:09 . Reden: minimum -> mex (thanks Soultaker voor het keyword 8)7 ) ]

[Soultaker]

Ghehe schreef op maandag 28 januari 2013 @ 21:02:
(^ als ik minimum zeg, bedoel ik dus het laagste getal dat er niet inzit)

Dat is helemaal niet verwarrend ofzo

De technische term die hier meestal voor gebruikt wordt is mex (afkorting van minimum excluded ordinal).

[Ghehe]

Soultaker schreef op maandag 28 januari 2013 @ 21:07:
[...]

Dat is helemaal niet verwarrend ofzo

De technische term die hier meestal voor gebruikt wordt is mex (afkorting van minimum excluded ordinal).

Heb het veranderd.

[- peter -]

Hmm, begrijp ik t goed dat de vinkjes op het scoreboard nog helemaal niets zeggen over of je ingeleverde output goed is? Ik zie nergens kruisjes bij mensen staan.

[kokx]

Nu het toch allemaal afgelopen is, heb ik mijn oplossingen maar eens online gezet. Heb er ook even een simpele beschrijving van de oplossing van alle problemen bijgezet, hoewel ik het vrij snel geschreven heb. Als je dus op- en/of aanmerkingen hebt, laat het dus maar weten!

@peter: Nee, inderdaad. Dit word allemaal naderhand pas gejudged (om cheaten te voorkomen, bijvoorbeeld mensen die dubbele accounts gebruiken om te checken of hun oplossingen correct waren).

[Soultaker]

Ik heb ook een weblogpost aan de problemen gewijd.

@kokx: het valt me op dat jouw oplossingen voor de laatste twee problemen probleem B relatief lomp is qua runtime performance. Nu scheelt het dat je C++ gebruikt, maar in Python kom je daar niet zomaar mee weg.

[kokx]

@Soultaker: Ik heb ook echt niet bizar veel geoptimaliseerd. Ik heb gewoon simpelweg de gemakkelijkste oplossing genomen die snel genoeg is. Mijn idee was ook vooral om er niet veel tijd in te steken, maar toch alle problemen te doen.

Ik betwijfel trouwens of C++ vs Python zoveel scheelt daarin hoor. Als je het met exact dezelfde datastructuren implementeerd (geen idee of dat zo gemakkelijk te doen is met Python), zal de running time als het goed is echt niet exponentieel groter zijn.

[ Voor 35% gewijzigd door kokx op 29-01-2013 01:25 ]

[Soultaker]

Ik vind het prima (hoe meer Tweakers zich kwalificeren, hoe beter!) maar realiseer je wel dat als ze bij Facebook snugger genoeg waren geweest om testcases als:

(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:q)))))))))))))))))))))))))))))))))

...of:

(x:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(

...of iets dergelijks toe te voegen, je een probleem had gehad.

kokx schreef op dinsdag 29 januari 2013 @ 01:20:
Ik betwijfel trouwens of C++ vs Python zoveel scheelt daarin hoor. Als je het met exact dezelfde datastructuren implementeerd (geen idee of dat zo gemakkelijk te doen is met Python), zal de running time als het goed is echt niet exponentieel groter zijn.

Da's waar.

Je oplossing voor het laatste probleem is trouwens wel prima — die had ik zo snel even verkeerd ingeschat. Je kunt je oplossing voor B ook makkelijk fixen door de tussenresultaten van parse() voor elke combinatie van p en depth te cachen. Dan heb je een O(|s|³) oplossing, wat goed te doen is voor |s| ≤ 100.

[ Voor 57% gewijzigd door Soultaker op 29-01-2013 01:36 ]

[Soultaker]

_{Doe maar deze trashen.}

[ Voor 90% gewijzigd door Soultaker op 29-01-2013 01:34 ]

[kokx]

@Soultaker: Ik had dat geval zo-even niet gezien . Of eigenlijk, vooral dat er overlapping subproblems zijn en memoization dus gewenst is.

Dat 'Find The Min' een beetje lomp eruit ziet, komt ook omdat ik die initieel vrij lomp geprogrammeerd had. Ik wist dat dat nooit snel genoeg ging zijn, maar ik zat eerst fout, en had het idee dat de eerste k (buiten de gegeven sequence) genereren genoeg zou zijn, maar even later kwam ik er pas achter dat die sequence zich elke k+1 herhaalt. En toen had ik die code, en heb ik die gewoon aangepast zodat ie werkte. Lelijk, dat wel, maar het werkte .

[ Voor 62% gewijzigd door kokx op 29-01-2013 07:19 ]

[Woy]

Doen ze eigenlijk nog iets met de code die je geupload hebt, of is dat alleen ter controle bij eventuele twijfelgevallen?

Ik twijfelde namelijk in welk format ik het moest uploaden, heb nu gewoon alleen de main program file ( waar alle code in staat ) geupload, dat leek me voldoende.

[HuHu]

Ik denk een snelle plagiaat-controle.

[Elijan9]

Beautiful Strings heb ik helaas niet kunnen uploaded binnen de tijd door browser problemen, maar dit was het belangrijkste stuk code:

C++: beautiful_strings.cpp

unsigned best_score(const std::string& str)
{
    unsigned result = 0;
    std::vector<unsigned> count_chars(26, 0);

    // Make a occurence list for all alphabet numbers
    for (int i = 0; i < str.size(); ++i) {
        char ch = str[i];
        if (isalpha(ch))
            count_chars[tolower(ch) - 'a'] += 1;
    }

    // sort the table in decreasing order
    std::sort(count_chars.begin(), count_chars.end());
    // calculate result
    for (int i = 0; i < 26; ++i)
        result += (i + 1) * count_chars[i];

    return result;
}

[ Voor 31% gewijzigd door Elijan9 op 30-01-2013 11:39 ]

[MrHaas]

Ik ben ook weer van de partij. Wilde gister 2 nog doen,maar buikgriepje voorkwam dat helaas. Bij 3 heb ik net iets andere methode, ik begin achterin de initielele array en gebruik alleen een lijst met missing. Voor elk getal in de initiele array kijk ik of het kleiner is dan K + 1 en of deze nog niet is toegevoegd, indien waar, dan voeg ik m toe aan het begin, zo niet, dan pop ik de hoogste value van de missing array. Op die manier hoef je niet bij te houden hoe vaak elk getal voorkomt.

Ik gebruikte alleen een gewone list om de missings bij te houden, dus de lookups en de removes waren te langzaam. 1 case deed ie 2.5 minuut over in Python, de rest ging in notime.

/edit: implementatie van 3 met blist runt in 8.5s
/edit2: en nog wat optimalisatie in 4s, code: https://gist.github.com/4663497

[ Voor 8% gewijzigd door MrHaas op 29-01-2013 12:10 ]

[kokx]

Woy schreef op dinsdag 29 januari 2013 @ 07:49:
Doen ze eigenlijk nog iets met de code die je geupload hebt, of is dat alleen ter controle bij eventuele twijfelgevallen?

Ik twijfelde namelijk in welk format ik het moest uploaden, heb nu gewoon alleen de main program file ( waar alle code in staat ) geupload, dat leek me voldoende.

Dat ligt er een beetje aan. Mij lijkt dat ze voor de qualificatieronde echt niet alle code door gaan kijken. Misschien dat ze wel checken of 2 mensen dezelfde code hebben (met een progamma). Maar mij lijkt dat ze echt wel kijken naar de code van de 25 mensen die naar de finale mogen.

Overigens kun je straks (als alles gejudged is) ook de code zien van iedereen. Dan kun je gewoon klikken op het vinkje, en kun je zo zien hoe die persoon die opgave opgelost heeft.

[sub0kelvin]

Ik heb uiteindelijk alleen de eerste ingestuurd. Die had ik redelijk rap opgelost. De laatste ook opgelost, maar helaas net buiten de 6 minuten. Ik had zelf wat moeilijke testcases toegevoegd, maar blijkbaar 1 dimensie over het hoofd gezien waardoor sommige cases toch langer duurden dan ik had verwacht.

Ach, hopelijk is die ene goed zodat ik nog steeds mee mag doen.

[Woy]

Mmm, de volgende ronde is zaterdag om 19:00, dat komt eigenlijk niet echt uit, en die week erna heb ik al helemaal geen tijd ( i.v.m. carnaval ).

Wat zijn de criteria om bij de volgende rondes door te gaan? Die kan ik nergens in de faq vinden.

[- peter -]

Ik vond opdracht 2 niet te doen, ik kreeg daar maar niet een goed idee bij. Moet nog veel leren blijkbaar
Opdracht 3 had ik uiteindelijk wel een best coole oplossing. Hij draaide in 0.4 seconde op de final input op mijn i5 (en dat in Ruby!) Nu hopen dat ie goed is, de testinputs gingen prima.

Ik vond dat je die K..2K rij kon generen door een array van 0..K aan te maken (dat zijn alle mogelijke waarden in die K..2K rij) en dan vanaf achteren telkens die waarde vergelijkt met de initiele M waarde op die positie. Als de M waarde kleiner is, dan moet die op die positie worden ingevoegd en de eerdere vermelding verwijderd worden. Als je dan vervolgens ook met een Hashset bijhoudt welke items je al verwijderd hebt, dan zorg je er ook voor dat je ze niet opnieuw later dubbel invoegt.

Als ik het zo goed kan zien zit je dan op een O(n%k) oplossing. Maar goed, daar heb ik niet veel kaas van gegeten.

https://gist.github.com/4664626

[Sneezydevil]

Volgens mij was het vorig jaar 45 Punten of meer door naar de volgende ronde? Is dat dit jaar weer?

Mijn oplossing voor probleem 2 leek erg op die van: Elijan9

Ik had eerst een andere aanpak, maar zag al snel dat ik in de problemen ging komen als ze testcases hadden gebruikt zoals Soultaker hierboven liet zien, ik heb het toen maar even herschreven.

[Eärendil]

Dit was mijn oplossing voor opdracht 3, draaide in 0.65s op de final input:

Python:

import sys

def find_the_min(n,k,a,b,c,r):
    # generate the first k values with the PRNG
    m = [a]
    for i in range(k-1):
        m.append((b*m[i]+c)%r)

    # find all values in m
    # with the value <= the index
    idx = {}
    for i in range(k):
        if m[i] <= i:
            idx[m[i]] = i

    # initialize 'mk' (second part of m, m[k..2*k])
    mk = [-1]*(k+1)
    # for all values in 'idx' the position is already known:
    for v,i in idx.iteritems():
        mk[i+1] = v

    y = 0
    for i in range(k+1):
        if mk[i] < 0:
            while y in idx:
                y += 1
            mk[i] = y
            y += 1

    return mk[(n-k)%(k+1)-1]

m = int(sys.stdin.readline())
for i in range(1,m+1):
    n,k = map(int, sys.stdin.readline().split())
    a,b,c,r = map(int, sys.stdin.readline().split())
    res = find_the_min(n,k,a,b,c,r)
    print 'Case #%d: %s' % (i, res)

@- peter -: jouw code geeft een andere output dan die van Soultaker en mij

[ Voor 12% gewijzigd door Eärendil op 29-01-2013 19:02 . Reden: code iets geoptimaliseerd ]

[- peter -]

Hmm, dan zit er toch iets mis. Jammer...

edit
Hmm, heb net jouw script gedraaid op dezelfde input, en toen mijn script, en de uitslag was identiek.
Misschien zit er iets fout in mijn gecleande code die ik heb geupload. Het originele script had meer debug output. Ik zal het wel uploaden in die gist.

Geupdate: https://gist.github.com/4664626

Mogelijk dat er bij jou iets misging met de input variabelen volgorde? (a,b,c,r,k,n )

[ Voor 103% gewijzigd door - peter - op 29-01-2013 16:50 ]

[kokx]

Woy schreef op dinsdag 29 januari 2013 @ 15:31:
Mmm, de volgende ronde is zaterdag om 19:00, dat komt eigenlijk niet echt uit, en die week erna heb ik al helemaal geen tijd ( i.v.m. carnaval ).

Wat zijn de criteria om bij de volgende rondes door te gaan? Die kan ik nergens in de faq vinden.

Voor de qualificatie is het altijd hetzelfde: zorg dat je tenminste 1 opgave goed hebt.

Vorig jaar, als ik het me goed herinner, was het zo dat als je in de eerste ronde bij de eerste 1000 of 500 hoorde, dat je door ging. Maar evenveel opgaven goed als de nr 1 was ook voldoende toen. Verdere rondes werden in die zin steeds sterker qua eisen.

[Soultaker]

- peter - schreef op dinsdag 29 januari 2013 @ 15:31:
Opdracht 3 had ik uiteindelijk wel een best coole oplossing.

Vind ik ook! Op m'n weblog commente iemand met een uitleg daarvan. Het komt er op neer dat je het probleem omkeert: in plaats van elementen van M in volgorde te genereren, plaats je de waarden zelf van 0 tot K op de juiste plaats in de array. Maar jouw code lijkt wat ingewikkelder dan nodig, omdat je van achter naar voren wil werken om één of andere reden...

Als ik het zelf implementeer kom ik hier op uit (wat sneller en korter is dan de oplossing die ik ingestuurd had):

Python:

import sys

cases = int(sys.stdin.readline())
for case in range(1, cases + 1):
    N, K       = map(int, sys.stdin.readline().split())
    a, b, c, r = map(int, sys.stdin.readline().split())

    M = { 0: a }
    for i in range(1, K):
        M[i] = (M[i - 1]*b + c)%r

    idx = dict((v, i + K + 1) for (i,v) in M.items())

    i = K
    for v in range(0, K + 1):
        M[max(i, idx.get(v))] = v
        while i in M:
            i += 1

    print('Case #{}: {}'.format(case, M[K + (N - K)%(K + 1) - 1]))

Als ik het zo goed kan zien zit je dan op een O(n%k) oplossing.

Hij is O(K), niet O(N%K), maar dat is dan ook optimaal. (Aangenomen dat je geen aannamen doet over de uitvoer van de RNG.)

kokx schreef op dinsdag 29 januari 2013 @ 12:01:
Overigens kun je straks (als alles gejudged is) ook de code zien van iedereen. Dan kun je gewoon klikken op het vinkje, en kun je zo zien hoe die persoon die opgave opgelost heeft.

Oh, dat werkt tegenwoordig? Ik had nog overwogen om een inzending in Brainfuck te doen.

[Eärendil]

Soultaker schreef op dinsdag 29 januari 2013 @ 17:13:
[...]
Als ik het zelf implementeer kom ik hier op uit (wat sneller en korter is dan de oplossing die ik ingestuurd had):

Python:

for v in range(0, K + 1):
   M[max(i, idx.get(v))] = v
   while i in M:
        i += 1

Hij is O(K), niet O(N%K), maar dat is dan ook optimaal. (Aangenomen dat je geen aannamen doet over de uitvoer van de RNG.)
[...]

Dat neemt aan dat een __setitem__(), __getitem__() en __contains__() op de dict O(1) operaties zijn, wat ze in worst case niet zijn. Ik weet niet of dat in dit geval uit maakt.

Mijn code (zie hierboven) gebruikt alleen voor de idx een dictionary, en gebruikt voor M een list. Ook sla ik in de index alleen waardes op die relevant zijn (m[i] <= i). Levert bij elkaar ruim twee keer zo snelle code op.

Het idee is verder vergelijkbaar, alleen vul ik de array uiteindelijk op volgorde van keys, niet op volgorde van values.

[Soultaker]

't Kan ook best alleen met arrays; ik gebruikte dict zodat ik niet van te voren na hoefde te denken over de bounds van de arrays en ik de in-operator handig kon gebruiken om te bepalen of een element al geïnitialiseerd was. Zo is het inderdaad mooier:

Python:

import sys

cases = int(sys.stdin.readline())
for case in range(1, cases + 1):
    N, K       = map(int, sys.stdin.readline().split())
    a, b, c, r = map(int, sys.stdin.readline().split())

    M = (K + K + 1)*[None]
    idx = (K + 1)*[K]
    for i in range(K):
        M[i] = a
        if a < K:
            idx[a] = i + K + 1
        a = (a*b + c)%r
    for v in range(0, K + 1):
        while M[i] is not None:
            i += 1
        if i >= idx[v]:
            M[i] = v
        else:
            M[idx[v]] = v

    print('Case #{}: {}'.format(case, M[K + (N - K)%(K + 1) - 1]))

Jouw versie is nog wel iets sneller, trouwens. Maar 't is snel zat.

Dat neemt aan dat een __setitem__(), __getitem__() en __contains__() op de dict O(1) operaties zijn, wat ze in worst case niet zijn.

Da's nogal pedantisch. De verwachtte tijdcomplexiteit is wel O(1) (dat is het sterke punt van hashtables) en het is onwaarschijnlijk dat er testcases zijn die een specifieke hashtable-implementatie exploiteren, zeker in Python, waarvan de hashtable implementatie een bijzonder goede collision resolution strategy heeft (veel beter dan PHP en zelfs Java, bijvoorbeeld).

Ik denk dus dat je hier best uit mag gaan van O(1) hashtable operaties. Een ander leuk weetje: in Python hashen integers naar zichzelf (en worden hash table buckets geindexeert door de hashcode modulo het aantal buckets te nemen) waardoor een dict waarvan de keys bestaan uit aansluitende natuurlijke getallen gegarandeerd geen collisions bevat. (De dict M in de code die ik eerder postte heeft daardoor gegarandeerd O(1) perfomance.)

Eärendil schreef op dinsdag 29 januari 2013 @ 19:37:
Het idee is verder vergelijkbaar, alleen vul ik de array uiteindelijk op volgorde van keys, niet op volgorde van values.

Oh ja, ik had me niet direct gerealiseerd dat het feit dat een element (zeg, x) als laatste op index i (x ≤ i < K) voorkomt, dat dat betekent dat hij ook exact op index i + K terecht komt! (In mijn code ging ik er alleen vanuit dat 'ie op een index ≥ i + K moet voorkomen, wat ook klopt, maar dat is een minder sterke uitspraak.)

Jouw oplossing kan trouwens ook best zonder hashtable, maar daar wordt 'ie niet eens sneller van!

[ Voor 14% gewijzigd door Soultaker op 29-01-2013 21:18 ]

[Ghehe]

Scores voor de kwalificatieronde zijn er: https://www.facebook.com/...ard?round=185564241586420

[Eärendil]

De uitslag van de kwalificatieronde staat online: https://www.facebook.com/...185564241586420&target=me

Ik had alle opgaven goed, net als 1092 anderen, waaronder Soultaker.
In totaal hebben 10170 van de 11392 deelnemers zich gekwalificeerd voor de eerste ronde door 1 of meer opgaven goed te hebben.

[SaphuA]

.

[ Voor 99% gewijzigd door SaphuA op 31-01-2022 15:06 ]

[kokx]

Mooi. Ondanks de grote hoeveelheid bugs in mijn code, was de output blijkbaar wel correct, van alle 3 de programma's .

[ Voor 12% gewijzigd door kokx op 30-01-2013 11:11 ]

[- peter -]

Hmm, blijkbaar ging er toch iets fout in mijn oplossing voor 3. Die is niet goedgekeurd. Helaas.
Blijkt 1 van de 20 waarden verkeerd als output. Heel vreemd.

Wel nummer 1 goed.

[ Voor 23% gewijzigd door - peter - op 30-01-2013 13:24 ]

[- peter -]

Het blijkt dat het dit jaar dus gaat om de top 500 mensen die door kunnen gaan (aan de hand van de scores en de timepenalty). En niet dus 500 + iedereen met evenveel goede oplossingen als 500.

Dat betekend dat je in feite dus echt moet beginnen als de 1e ronde begint. Ik weet niet hoe laat dat is in NL?

Ik vind het wel een slechte zaak. Het was juist fijn dat je op je eigen moment kon meedoen.

[ Voor 13% gewijzigd door - peter - op 01-02-2013 17:44 ]

[wjvds]

- peter - schreef op vrijdag 01 februari 2013 @ 17:44:
Dat betekend dat je in feite dus echt moet beginnen als de 1e ronde begint. Ik weet niet hoe laat dat is in NL?

http://www.timeanddate.co...1&iso=20130202T10&p1=1240

Morgenavond, 7 Nederlandse tijd dus.

[Soultaker]

Iedereen hard aan het werk, neem ik aan?

[Woy]

Helaas geen tijd nu, ik kijk morgen ochtend nog wel even, maar dan heb ik natuurlijk al geen enkele kans meer om door te gaan naar de volgende ronde.

[MrHaas]

Jep, 2 gedaan, op naar laatste...

[sub0kelvin]

Ik ben begonnen met de laatste. Nog bezig en volgens mij halverwege een nette oplossing die de restricties aan kan.

[Soultaker]

Zo, ik heb ze alledrie gesubmit. Deze keer wat meer tijd genomen om m'n oplossingen te dubbelchecken zodat alles hopelijk goed is deze keer (in tegenstelling tot vorig jaar, toen ik één karakter verkeerd getypt had.)

edit:
Voor wie nog bezig is: succes! Ik schat zo in dat als je voor middernacht alledrie de opgaven ingeleverd, je wel in de top 500 kunt eindigen. Dus zet 'm op

[ Voor 32% gewijzigd door Soultaker op 02-02-2013 21:48 ]

[MrHaas]

Tx, leuke opgaven deze ronde btw!

[Jegorex]

Is het niet zo dat iedereen die evenveel punten heeft als de nr500 ook door gaat naar de volgende ronde?
Azie is nu enorm in het nadeel omdat het daar nacht is.

[Soultaker]

Nope, dat werd hier juist expliciet gezegd. Jammer voor Azië inderdaad.

[ Voor 11% gewijzigd door Soultaker op 02-02-2013 22:19 ]

[MrHaas]

Zo, finished, ben benieuwd

/edit: net op laatste moment geresubmit omdat ik zag dat ik perongeluk output van problem 2 bij 3 had gesubmit

[ Voor 67% gewijzigd door MrHaas op 02-02-2013 23:02 ]

[Soultaker]

Goed dat je 't nog op tijd zag.

[frG]

Kan iemand mij uitleggen wat ze bedoelen met modulo 1 000 000 007 ?
Ik ken de mod operator, maar snap niet hoe ze het bedoelen op deze manier..

[ Voor 36% gewijzigd door frG op 02-02-2013 23:09 ]

[MrHaas]

Dat je de som van de maximale elementen nog modulo 1000000007 moet doen, dus stel dat de som 1000000008 is, is het antwoord 1

[MrHaas]

407e sta ik nu, dus iig top 500 als ik ze allemaal goedheb

[Drak0z]

Ik heb iig het Security probleem opgelost. De dead pixels heb ik een suboptimale oplossing, die wil ik nog gaan verbeteren (en heb ik derhalve nog niet gesubmit). Ik breek alleen m'n kop over wat ze nou in 's hemelsnaam willen bij die CardGame... Ik heb net m'n eerste biertje gepakt, misschien helpt dat met nadenken ;-)