Facebook Hacker Cup 2013 Vorige deel Overzicht Volgende deel Laatste deel

Dit topic is onderdeel van een reeks. Ga naar het meest recente topic in deze reeks.

Pagina: 1 2 Laatste
Acties:

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

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

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

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?

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
De andere opdrachten had ik al correct ingestuurd.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • Pizzalucht
  • Registratie: Januari 2011
  • Laatst online: 09:07

Pizzalucht

Snotneus.

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.

Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
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...

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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.

Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
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 ).

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
spoiler:
*previous* *k* values of m

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


Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015

Acties:
  • 0 Henk 'm!

  • wjvds
  • Registratie: Mei 2012
  • Laatst online: 13-06 07:41
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.

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
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.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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.

Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
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 ]


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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.)

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
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.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • SaphuA
  • Registratie: September 2005
  • Laatst online: 06-05 16:40
.

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


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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 ]


Acties:
  • 0 Henk 'm!

  • Elijan9
  • Registratie: Februari 2004
  • Laatst online: 14:09
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 ]

War is when the young and stupid are tricked by the old and bitter into killing each other. - Niko Bellic


Acties:
  • 0 Henk 'm!

  • Ghehe
  • Registratie: April 2011
  • Laatst online: 09-06 22:12

Ghehe

400 pound hacker

Topicstarter
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 ) ]


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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).

Acties:
  • 0 Henk 'm!

  • Ghehe
  • Registratie: April 2011
  • Laatst online: 09-06 22:12

Ghehe

400 pound hacker

Topicstarter
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. :>

Afbeeldingslocatie: http://cl.ly/image/3T2d193y2H1Z/you_didnt_see_anything.gif

Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
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.

Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

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

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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. ;)

Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

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


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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|3) oplossing, wat goed te doen is voor |s| ≤ 100.

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


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Doe maar deze trashen.

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


Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

@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 :D.

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


Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
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.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • HuHu
  • Registratie: Maart 2005
  • Niet online
Ik denk een snelle plagiaat-controle.

Acties:
  • 0 Henk 'm!

  • Elijan9
  • Registratie: Februari 2004
  • Laatst online: 14:09
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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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 ]

War is when the young and stupid are tricked by the old and bitter into killing each other. - Niko Bellic


Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
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 ]


Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

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.

Acties:
  • 0 Henk 'm!

  • sub0kelvin
  • Registratie: September 2002
  • Laatst online: 10-08-2023
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.

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
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 :P ).

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

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
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

Acties:
  • 0 Henk 'm!

  • Sneezydevil
  • Registratie: Januari 2002
  • Laatst online: 28-11-2024
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.

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
Dit was mijn oplossing voor opdracht 3, draaide in 0.65s op de final input:

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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 ]


Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
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 ]


Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

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 :P ).

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.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
- 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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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. :+

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
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:
1
2
3
4
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.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
'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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 ]


Acties:
  • 0 Henk 'm!

  • Ghehe
  • Registratie: April 2011
  • Laatst online: 09-06 22:12

Ghehe

400 pound hacker

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

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
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.

Acties:
  • 0 Henk 'm!

  • SaphuA
  • Registratie: September 2005
  • Laatst online: 06-05 16:40
.

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


Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

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

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


Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
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 ]


Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
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 ]


Acties:
  • 0 Henk 'm!

  • wjvds
  • Registratie: Mei 2012
  • Laatst online: 13-06 07:41
- 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.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Iedereen hard aan het werk, neem ik aan?

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
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.

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Jep, 2 gedaan, op naar laatste...

Acties:
  • 0 Henk 'm!

  • sub0kelvin
  • Registratie: September 2002
  • Laatst online: 10-08-2023
Ik ben begonnen met de laatste. Nog bezig en volgens mij halverwege een nette oplossing die de restricties aan kan.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
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 ]


Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Tx, leuke opgaven deze ronde btw!

Acties:
  • 0 Henk 'm!

  • Jegorex
  • Registratie: April 2004
  • Laatst online: 18:03
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.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Nope, dat werd hier juist expliciet gezegd. Jammer voor Azië inderdaad.

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


Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
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 ]


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
:o Goed dat je 't nog op tijd zag.

Acties:
  • 0 Henk 'm!

  • frG
  • Registratie: Augustus 2004
  • Laatst online: 15-06 09:38

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 ]


Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Dat je de som van de maximale elementen nog modulo 1000000007 moet doen, dus stel dat de som 1000000008 is, is het antwoord 1

Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
407e sta ik nu, dus iig top 500 als ik ze allemaal goedheb :P

Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
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 ;-)

Acties:
  • 0 Henk 'm!

  • CodeCaster
  • Registratie: Juni 2003
  • Niet online

CodeCaster

Can I get uhm...

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

https://oneerlijkewoz.nl
Het ergste moet nog komen / Het leven is een straf / Een uitgestrekte kwelling van de wieg tot aan het graf


Acties:
  • 0 Henk 'm!

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

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

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


Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
@Soultaker - Bonuspoints voor het snappen van de referentie ;-)
@CodeCaster - Volgens mij snap ik hem nu... Ik zal het zo even uitwerken, maar ik kwam er vooral niet uit dankzij het voorbeeld :-)

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
Ik heb net de laatste ingeleverd. Ik sta nu 589, dus als ik alles goed heb en genoeg anderen hebben fouten gemaakt… :p
Nadeel is dat ik natuurlijk ook nog weer kan zakken als iemand die sneller was met de eerste opdrachten ook nog de laatste inlevert.

Acties:
  • 0 Henk 'm!

  • frG
  • Registratie: Augustus 2004
  • Laatst online: 15-06 09:38

frG

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

Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Helaas een foutje ontdek in 3, dus die heb ik sowieso fout. Balen...:(

Acties:
  • 0 Henk 'm!

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

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

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

Acties:
  • 0 Henk 'm!

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

Acties:
  • 0 Henk 'm!

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

Acties:
  • 0 Henk 'm!

  • xos
  • Registratie: Januari 2002
  • Laatst online: 10-06 12:27

xos

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

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

Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
xos - Dit is de huidige ronde van de Cup. Ik schat niet dat het nu werkt, maar misschien vanaf 19:00 :)
https://www.facebook.com/...php?round=189890111155691

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

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


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Zo, ik heb alvast mijn oplossingen online gezet. Ik zal er later vanavond nog een paar voorbeeldjes in editen; ik weet niet of de tekstuele beschrijving heel goed te volgen is.

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

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


Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
@Soultaker: Mooi om te zien dat je qua kaartenprobleem (bijna?) dezelfde ideeen had als ik.
Mijn oplossing voor Card Game (in pseudo-java):
spoiler:
TreeList (= sorted list) vullen met kaarten
MaxHanden berekenen door fac(n)/(fac(n-k)*(fac(k)))
k--;
zolang het aantal handen > 0 is en ik nog kaarten heb:
pak de laatste kaart (sorted list dus altijd hoogste waarde)
n--;
result += kaartwaarde*min(MaxHanden, fac(n)/(fac(n-k)*(fac(k))));
MaxHanden -= fac(n)/(fac(n-k)*(fac(k)));

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


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

Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Mijn oplossingen in Python: https://gist.github.com/63b92ee871fe975446d1

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Nette code, maar ik volg niet helemaal wat je bij Security precies probeert te doen, en volgens mij klopt 't ook niet helemaal, want ik krijg er net wat andere uitvoer uit. Bijvoorbeeld voor deze testcase:
27
?dd???ea???a?aadfade??d??fe?a??ecd????af??ccaaac??adb?
?ab?ad??a???e?be????db????d?f?db??de?c???dcd?f??c?b??a

Mijn antwoord:
addaaaeaaaaaaaadfadeaadaafeaaaaecdbabaafdbccaaacdbadbe


Jouw antwoord:
addaaaeaaaaaaaadfadeaadabfeaaabecddadbafdbccaaacfaadbe


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

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
Ik heb 1 en 3 denk ik goed, en 2 fout. Ik kreeg veel te vaak 'IMPOSSIBLE' op de uiteindelijke input, en dacht al dat ik hier fout zat, maar had geen tijd om mijn fout te zoeken in 6 minuten.

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

Mijn oplossing voor de dead_pixels was ongeveer dit:
  • Reken de posities van de dead pixels uit en sla ze op in een map van kolomnr -> set van rijnummers
  • Initialiseer een kolom-vector met elke rij = 0
  • Voor alle kolommen:
    • als het rijnummer niet in de set van rijnummers van deze kolom zit => rij-waarde++
    • als het rijnummer wel in de set van rijnummers van deze kolom zit => rij-waarde = 0
    • maximum rij-waarde is de breedte van het te plaatsen blokje
    • elke range met waarde van minimaal breedte van het te plaatsen blokje en lengte van de range van minimaal hoogte van het te plaatsen blokje => verhoog uiteindelijke resultaat met aantal keer dat de hoogte in die range past
Als voorbeeld een scherm van 6x5, dode pixel in het midden en een te plaatsen blok van 3x2:
000000      123456      123333
000000      123456      123333
001000  =>  120123  =>  120123
000000      123456      123333
000000      123456      123333

Omdat het aantal dead pixels relatief laag is vergeleken met het totaal aantal pixels, kan dit sparse worden opgeslagen (elke rij is een kolom uit de bovenstaande tabel):
[(0,4,1)]
[(0,4,2)]
[(0,1,3), (2,2,0), (3,4,3)]
[(0,1,3), (2,2,1), (3,4,3)]
[(0,1,3), (2,2,2), (3,4,3)]
[(0,1,3), (2,2,3), (3,4,3)] = [(0,4,3)]

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

Acties:
  • 0 Henk 'm!

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

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

Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Soultaker schreef op zondag 03 februari 2013 @ 21:15:
[...]

Nette code, maar ik volg niet helemaal wat je bij Security precies probeert te doen, en volgens mij klopt 't ook niet helemaal, want ik krijg er net wat andere uitvoer uit. Bijvoorbeeld voor deze testcase:
27
?dd???ea???a?aadfade??d??fe?a??ecd????af??ccaaac??adb?
?ab?ad??a???e?be????db????d?f?db??de?c???dcd?f??c?b??a

Mijn antwoord:
addaaaeaaaaaaaadfadeaadaafeaaaaecdbabaafdbccaaacdbadbe


Jouw antwoord:
addaaaeaaaaaaaadfadeaadabfeaaabecddadbafdbccaaacfaadbe


De 25e letter is bij mij een 'a' en bij jouw een 'b'.
Ja, zag t ook, waarschijnlijk pak ik niet de optimale sequence qua alfabetische volgorde.

Acties:
  • 0 Henk 'm!

  • Drak0z
  • Registratie: November 2002
  • Laatst online: 02-02-2015
Zoals verwacht was mijn oplossing voor Security fout. Ik moet nog uitzoeken wat ik fout deed, maar dat komt na m'n werk.

Mijn idee bij de Dead Pixels (waar ik uiteindelijk op vast kwam te zitten); letterlijke copy/paste uit mijn code
Java: deadpixels.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
numPossibilities = (w-p+1)*(h-q+1);

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

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



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

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
Ik had problem 2 zoals verwacht fout en val daarmee dus buiten de 500.
Heeft er behalve Soultaker nog iemand anders de volgende ronde gehaald?

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Dat die vraag onbeantwoord blijft voorspelt niet veel goeds...
Woy schreef op zaterdag 02 februari 2013 @ 20:48:
Helaas geen tijd nu, ik kijk morgen ochtend nog wel even, maar dan heb ik natuurlijk al geen enkele kans meer om door te gaan naar de volgende ronde.
Dat bleek achteraf dus best mee te vallen!

Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Soultaker schreef op maandag 04 februari 2013 @ 22:34:
Dat die vraag onbeantwoord blijft voorspelt niet veel goeds...


[...]

Dat bleek achteraf dus best mee te vallen!
Ja, inderdaad, had ik maar iets meer tijd genomen om problem 3 nog x te testen...

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

Succes btw in de volgende ronde!

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


Acties:
  • 0 Henk 'm!

  • - peter -
  • Registratie: September 2002
  • Laatst online: 05-06 19:31
Wow Soultaker, je blog is gelinked in de uitleg van Facebook van ronde 1!

Acties:
  • 0 Henk 'm!

  • Woy
  • Registratie: April 2000
  • Niet online

Woy

Moderator Devschuur®
Soultaker schreef op maandag 04 februari 2013 @ 22:34:
Dat bleek achteraf dus best mee te vallen!
Nou heb ik 's ochtends ook niet echt gered :P

“Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.”


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Ronde 2 begint over twintig minuten, maar ik zie nog geen linkje... hoop dat ze 't niet vergeten zijn. :+

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

Acties:
  • 0 Henk 'm!

  • Ghehe
  • Registratie: April 2011
  • Laatst online: 09-06 22:12

Ghehe

400 pound hacker

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

In ieder geval: Veel geluk. :)

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Ah, nu zie ik 'm ook. Bedankt!

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

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

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


Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
En, wat is het geworden?

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

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Ik had uiteindelijk alleen het tweede probleem goed, en eindigde op de 236e plek. Toch nog in de bovenste helft :+ Het zijn wel leuke probleem op zich. Jullie kunnen ze nu ook zien neem ik aan?

Acties:
  • 0 Henk 'm!

  • iChaos
  • Registratie: December 2009
  • Laatst online: 18:17

iChaos

It's Lupus.

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

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 17:30
Project Euler is vrij bekend (maar leunt erg sterk op wiskunde, wat niet iedereen leuk vindt).

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

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

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

Acties:
  • 0 Henk 'm!

  • kokx
  • Registratie: Augustus 2006
  • Laatst online: 15-06 00:11

kokx

WIN

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

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

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

Acties:
  • 0 Henk 'm!

  • MrHaas
  • Registratie: Maart 2009
  • Laatst online: 13-06 21:17
Op de site van Google Code Jam kan je de opgaven van voorgaande jaren bekijken en laten checken.

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

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
De Hacker Cup 2014 begint al volgend weekend, dus twee maanden eerder dan vorige jaren:

RondeStartDuurEind
Online Qualification Roundvrijdag 22 november 01:0072 uurmaandag 25 november 01:00
Online Elimination Round 1zaterdag 7 december 19:0024 uurzondag 8 december 19:00
Online Elimination Round 2zaterdag 14 december 19:003 uurzaterdag 14 december 22:00
Online Elimination Round 3zaterdag 21 december 19:003 uurzaterdag 21 december 22:00
Onsite Finals at Facebook20 en 21 februari 2014

https://www.facebook.com/hackercup

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


Acties:
  • 0 Henk 'm!

Anoniem: 304426

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

Acties:
  • 0 Henk 'm!

  • Eärendil
  • Registratie: Februari 2002
  • Laatst online: 18:06
Ik heb voor de editie 2014 een nieuw topic aangemaakt: Facebook Hacker Cup 2014
Pagina: 1 2 Laatste