“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.”
Anoniem: 170251
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.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?
Helaas!
Misschien een andere opdracht alsnog goed insturen?
“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.”
Ga toch proberen de andere problemen correct in te sturen, 2 heb ik volgens mij goed gemaakt, op naar 3.
Mijn vraag is echter; maak ik een denkfout bij de 3e opdracht? Volgens mij matchen example inputs niet met example outputs...
Het maakt dus helemaal niet uit hoe snel of hoeveel opgaven je dit weekeinde oplost, als je er maar één correct oplost.
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 ).
[ Voor 80% gewijzigd door Eärendil op 26-01-2013 16:01 ]
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.
[ Voor 20% gewijzigd door - peter - op 26-01-2013 23:07 ]
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.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.
“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.”
[ Voor 101% gewijzigd door SaphuA op 31-01-2022 15:06 ]
[ Voor 47% gewijzigd door Soultaker op 28-01-2013 19:42 ]
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...

[ 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
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 ) ]
Dat is helemaal niet verwarrend ofzoGhehe schreef op maandag 28 januari 2013 @ 21:02:
(^ als ik minimum zeg, bedoel ik dus het laagste getal dat er niet inzit)
De technische term die hier meestal voor gebruikt wordt is mex (afkorting van minimum excluded ordinal).
Heb het veranderd.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).

@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).
@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.
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 ]
(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:q)))))))))))))))))))))))))))))))))
...of:
(x:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(:(
...of iets dergelijks toe te voegen, je een probleem had gehad.
Da's waar.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.
Je oplossing voor het laatste probleem is trouwens wel prima — die had ik zo snel even verkeerd ingeschat.
[ Voor 57% gewijzigd door Soultaker op 29-01-2013 01:36 ]
[ Voor 90% gewijzigd door Soultaker op 29-01-2013 01:34 ]
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 ]
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.”
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
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 ]
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.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.
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.
Ach, hopelijk is die ene goed zodat ik nog steeds mee mag doen.
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.”
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
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.
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 ]
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 ]
Voor de qualificatie is het altijd hetzelfde: zorg dat je tenminste 1 opgave goed hebt.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.
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.
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...- peter - schreef op dinsdag 29 januari 2013 @ 15:31:
Opdracht 3 had ik uiteindelijk wel een best coole oplossing.
Als ik het zelf implementeer kom ik hier op uit (wat sneller en korter is dan de oplossing die ik ingestuurd had):
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])) |
Hij is O(K), niet O(N%K), maar dat is dan ook optimaal.Als ik het zo goed kan zien zit je dan op een O(n%k) oplossing.
Oh, dat werkt tegenwoordig? Ik had nog overwogen om een inzending in Brainfuck te doen.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.
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.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.)
[...]
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.
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.
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).Dat neemt aan dat een __setitem__(), __getitem__() en __contains__() op de dict O(1) operaties zijn, wat ze in worst case niet zijn.
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.)
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.)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.
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 ]
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.
[ Voor 99% gewijzigd door SaphuA op 31-01-2022 15:06 ]
[ Voor 12% gewijzigd door kokx op 30-01-2013 11:11 ]
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 ]
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 ]
http://www.timeanddate.co...1&iso=20130202T10&p1=1240- 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?
Morgenavond, 7 Nederlandse tijd dus.
“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.”
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 ]
Azie is nu enorm in het nadeel omdat het daar nacht is.
[ Voor 11% gewijzigd door Soultaker op 02-02-2013 22:19 ]
/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 ]
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 ]
https://oneerlijkewoz.nl
Het ergste moet nog komen / Het leven is een straf / Een uitgestrekte kwelling van de wieg tot aan het graf
Ballmer peakDrak0z 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 ;-)
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 ]
@CodeCaster - Volgens mij snap ik hem nu... Ik zal het zo even uitwerken, maar ik kwam er vooral niet uit dankzij het voorbeeld :-)
Nadeel is dat ik natuurlijk ook nog weer kan zakken als iemand die sneller was met de eerste opdrachten ook nog de laatste inlevert.
Security vond ik verdacht makkelijk, daar zal ik wel iets fout gedaan hebben
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)
PS: Soultaker, leuke blogposts. Lees het met veel plezier.
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 ]
@Drak0z: jammer, maar je hebt tenminste geprobeert. Respect voor het doorwerken tot de deadline
[ Voor 9% gewijzigd door Soultaker op 03-02-2013 19:18 ]
Mijn oplossing voor Card Game (in pseudo-java):
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....

De andere twee zal ik later uitwerken... Nu eerst slapen!
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:MrHaas schreef op zondag 03 februari 2013 @ 19:34:
Mijn oplossingen in Python: https://gist.github.com/63b92ee871fe975446d1
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'.
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
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)
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
Ja, zag t ook, waarschijnlijk pak ik niet de optimale sequence qua alfabetische volgorde.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'.
Mijn idee bij de Dead Pixels (waar ik uiteindelijk op vast kwam te zitten); letterlijke copy/paste uit mijn code
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 :-)
Heeft er behalve Soultaker nog iemand anders de volgende ronde gehaald?
Dat bleek achteraf dus best mee te vallen!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.
Ja, inderdaad, had ik maar iets meer tijd genomen om problem 3 nog x te testen...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!
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 ]
Nou heb ik 's ochtends ook niet echt geredSoultaker schreef op maandag 04 februari 2013 @ 22:34:
Dat bleek achteraf dus best mee te vallen!
“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.”
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.
In ieder geval: Veel geluk.
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 ]
Ik ga morgen es kijken hoe ver ik kom...
• 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.
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.
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.
Ronde | Start | Duur | Eind |
---|---|---|---|
Online Qualification Round | vrijdag 22 november 01:00 | 72 uur | maandag 25 november 01:00 |
Online Elimination Round 1 | zaterdag 7 december 19:00 | 24 uur | zondag 8 december 19:00 |
Online Elimination Round 2 | zaterdag 14 december 19:00 | 3 uur | zaterdag 14 december 22:00 |
Online Elimination Round 3 | zaterdag 21 december 19:00 | 3 uur | zaterdag 21 december 22:00 |
Onsite Finals at Facebook | 20 en 21 februari 2014 |
https://www.facebook.com/hackercup
[ Voor 81% gewijzigd door Eärendil op 18-11-2013 01:39 ]