... en de ronde is voorbij! Ik dump gelijk maar een megapost met daarin mijn oplossingen:
Labelmaker
Als
b de lengte van de string
L is, dan zijn er precies
bn strings van lengte
n. Beginnend met
b=1 is het vrij makkelijk om te checken of
N ≤
bn. Zo ja, dan weten we de lengte van het antwoord. Zo niet, dan kunnen we die strings overslaan door
bn van
N af te trekken, en
b te verhogen.
Als we de lengte eenmaal bepaald hebben, kunnen we de string zelf bepalen door
N-1 te interpreteren als basis-
b getal met de letters uit
L als cijfers. (De -1 is hier omdat de eerste string nummer 1 heeft.)
In talen met 64-bit integers is het trouwens een enorm gepiel om dit goed te krijgen, omdat de invoer zo groot is dat integer overflow een risico is. (Gelukkig bevat de voorbeeldinvoer zo'n geval.)
Code in Python
Coins Game
Dit vond ik het leukste probleem. De optimale strategie (en daarmee de oplossing) is heel simpel, maar ligt niet meteen voor de hand.
Als alle potten minstens
x munten bevatten, kun je veilig uit elke pot
x munten pakken, dus doe je dat ook. Daarna zijn sommige potten leeg, en sommige niet. Om nog een muntje te kunnen pakken zul je, in het ongunstigste geval, eerst alle lege potten moeten ontdekken door er een actie aan te verspillen (je wijst de pot aan, maar hij blijkt leeg te zijn). Daarna kun je uit de overgebleven potten veilig 1 (of meer) muntje(s) halen.
Het moge duidelijk zijn dat aan deze strategie niets te verbeteren valt. Gegeven is dus dat je
m rondes uitvoert (waarbij je in een ronde uit elke pot 1 muntje probeert te pakken) tot je genoeg munten hebt verzameld, en maximaal 1 actie per pot verspilt (want als een pot leeg blijkt te zijn ga je er natuurlijk niet nog een keer uit pakken). De potten waar je geen actie aan verspilt zijn precies de potten die in de laatste ronde nog niet leeg blijken te zijn; daar zaten dus minstens
m munten in.
Om het aantal potten met
m munten te kunnen maximaliseren, moet je
m minimaliseren, onder de voorwaarde dat
m×
N ≥
C, omdat je anders na
m keer pakken uit
N potten niet genoeg munten hebt verzameld. De minimale waarde van
m is dus
C/N naar boven afgerond.
Het aantal potten dat je tot
m kan vullen is gelijk aan
K/m (naar beneden afgerond). Als dat aantal groter dan of gelijk aan
N is, ben je makkelijk klaar. Zoniet, dan zijn er precies
N - K/m potten waar je een actie aan moet verspillen, en omdat
m minimaal is, is
K/m maximaal, en is
N - K/m minimaal.
Code in Python
AAAAAA
Eerst berekenen we voor elke (lege) cel op positie (r,c) (r voor rij, c voor kolom) of 'ie bereikbaar is vanaf de ingang op 0,0 en wat de maximale lengte van een pad is dat begint op die cel, onder de aanname dat we alleen naar rechts en beneden mogen stappen. Die waarden stoppen we in arrays, genaamd
reach en
maxdist. Die arrays zijn makkelijk uit te rekenen door in het eerste geval steeds te kijken of er een cel links of boven bereikbaar is, en in het tweede geval door de maximale afstand rechts en onder de nemen. (De volgorde waarin arrays worden gevuld is daarbij van belang!)
Nu mogen we ook nog één horizontaal segment invoegen waarop naar links wordt gelopen, of één verticaal segment waarop naar boven wordt gelopen. Cruciale observatie is dat een horizontaal segment altijd van boven binnengegaan wordt, en naar beneden wordt verlaten. Een horizontaal segment van (r,c1)-(r,c2) dat uit lege cellen bestaat is dus bereikbaar als (r-1,c2) (de cel boven de rechterkant) bereikbaar is. De afstand tot de rechterkant is (r+c2), de lengte van het segment is (c2-c1+1), en de afstand vanaf de linkerkant wordt gegeven door
maxdist\[r+1][c1]. De situatie voor verticale segmenten is vergelijkbaar.
We kunnen in O(H×W×(H + W)) tijd alle mogelijke segmenten aflopen. Met twintig testcases en H,W ≤ 50 is dat in C++ of Java goed te doen, maar in bijvoorbeeld Python is dat helaas te traag.
Code in C++
Preventing Alzheimer's
Nu wordt het echt ingewikkeld. De kern van het probleem is het volgende: als we een lijst getallen hebben, hoe vaak moeten we dan een getal met 1 ophogen om een lijst te maken waarin elk paar getallen copriem is? Voordat we dat probleem oplossen is het handig om twee randgevallen uit de weg te ruimen:
- Als K > 1 dan moeten alle getallen een veelvoud van K zijn. Het is praktisch om alle getallen naar boven af te ronden naar een veelvoud van K en vervolgens te delen door K, zodat we altijd kunnen doen alsof K=1. (Dan moet het antwoord wel weer met K vermenigvuldigd worden.)
- Nullen in de invoer zijn vervelend. Als twee kinderen $0 krijgen is de oplossing ongeldig, want die zijn allebei deelbaar door alle getallen. We kunnen dus hooguit één kind $0 geven, en dan alleen als alle andere kinderen $1 krijgen (onder aanname dat K=1, zie hierboven). Zoniet, dan moeten we alle kinderen een bedrag >$0 geven.
Als we die gevallen hebben afgehandeld kunnen we er vanuit gaan dat K=1 en dat alle getallen groter dan 0 zijn. Dan het echte probleem. We hebben een array A en we willen een array B maken zodat A[i] ≤ B[i] voor alle indices
i, en zo dat gcd(B[i],B[j])=1 voor elk paar indices
i<
j, en zo dat de som van B minimaal is.
Een belangrijke observatie is dat er maximaal 20 getallen zijn, en geen getal is groter dan 50. Dat betekent dat als we 20 priemgetallen groter dan 50 pakken, we sowieso een geldige oplossing hebben. Concreet:
- Er zijn 15 kleine priemgetallen: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.
- En dan 20 grote priemgetallen: 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149.
We kunnen nu in principe bruteforce steeds een waarde tussen A[i] en 150 proberen toe te kennen, en dan checken of het gekozen getal copriem is met de al eerder gekozen getallen; zo ja, door naar het volgende getal. Dit werkt in principe, behalve dat het veel te traag is. Gelukkig zijn er nog een paar observaties mogelijk: elk getal in B[i] wordt ofwel een groot priemgetal, ofwel een combinatie van (0 of meer) kleine priemgetallen. Het is nooit nodig om grote en kleine priemgetallen te combineren; in plaats van bijvoorbeeld 206=2×53 kunnen we beter gewoon 53 pakken. Verder zijn alle grote priemgetallen groter dan 50, dus áls we er een gebruiken, kunnen we het beste de kleinste nemen die nog niet gebruikt is.
Nu komt de efficiënte oplossing in zicht. Als we van links naar rechts door de array lopen dan kunnen we op elke positie ófwel het volgende grote priemgetal invullen, ófwel een getal dat een combinatie is van kleine priemgetallen die nog niet eerder gebruikt zijn (mits dat getal groter is dan A[i]).
Elke toestand wordt dus gekenmerkt door: de positie in de lijst, de verzameling van kleine priemgetallen die al gebruikt zijn, en het
aantal grote priemgetallen dat gebruikt is (we gebruiken namelijk altijd de kleinste). Dat levert 20×2
15×20 = ~13 miljoen toestanden op, waarbij op elke positie <150 getallen uitgebrobeerd moeten worden (alle getallen tussen A[i] en het volgende grote priemgetal). Dat is maximaal twee miljard iteraties per test case, wat niet weinig is, maar in de praktijk vallen er een heleboel toestanden af, waardoor alles vlot draait mits geïmplementeerd in een snelle programmeertaal.
Code in C++
:strip_exif()/u/48440/crop6130a5af754ae_cropped.webp?f=community)
:strip_exif()/u/62716/avatar.gif?f=community){kind=avatar}
:strip_exif()/u/138622/kikker.gif?f=community)
.
/u/200133/artemis_square_e_60-60.png?f=community)
Ik ga ook maar een poging wagen, verwacht er niet al te veel van maar ben benieuwd! 
:strip_exif()/u/402713/crop61a8df0bd950d_cropped.gif?f=community)
:strip_icc():strip_exif()/u/406524/test.jpg?f=community)
/u/64204/crop5e333d1575fff.png?f=community)
:strip_exif()/u/11775/SoulTaker.gif?f=community)
/u/262310/ava.png?f=community)
:strip_exif()/u/295549/crop56eca4759ac3c_cropped.gif?f=community)
:strip_icc():strip_exif()/u/6143/rincewind.jpg?f=community)
:strip_icc():strip_exif()/u/120006/acb1cf0156bfb0634b213bf0cb9b0ca556a60316_medium.jpg?f=community)
/u/106079/crop58c7cd975e5a1_cropped.png?f=community)
/u/22274/banaan60x60.png?f=community)
Ik ga nog maar eens letter voor letter uitpluizen hoe ze de 