Het tweede input/output voorbeeld geeft een leuke property aan. Het laat zien dat doordat je slechts
n-1 birdlocations hebt, je hier altijd overheen kunt komen aangezien je
n explosieven hebt welke niet dezelfde waarde mogen hebben. Ergo, als al je birdlocations consecutive zijn, bestrijken ze een afstand van maximaal
n-1 en je grootste explosief is
minimaal n.
Het eerste input/output voorbeeld is nogal klein, maar geeft wel het idee van nonconsecutive birdlocations. Je zult er dan namelijk tussendoor moeten springen als je explosieven kleine afstanden afleggen.
Bewijzen dat dit altijd mogelijk is, rust
denk ik op drie 'losse bewijzen' voor het eerste geval:
1. Als je één groot consecutive blok hebt van birdlocations, dan is dit altijd kleiner dan de grootst beschikbare explosie. Zoals ik aangaf in mijn eerste opmerking, het blok bestrijkt
n-1 punten en de grootste explosie is
n en 'overbrugt' daarmee dus
n-1 punten.
2. Als je één groot consecutive blok hebt van birdlocations dan heeft deze dus lengte
n-1 en begint op een bepaalde
X. Wanneer de grootst beschikbare explosief
n is, dan zijn de overige explosieven van grootte
n-1,
n-2,
...,
1. Te bewijzen is dat je met die verzameling altijd
X-1 kunt construeren, zodat je daarna explosief
n kunt activeren. Waarbij je weet welke waarden de
X aan kan nemen.
X is per definitie groter dan
0 en aangezien de birdlocations maximaal lopen tot
'som van alle explosiegroottes' - 1, is die waarde minus
n-1 de maximale waarde die
X aan kan nemen. Deze sommatie zal je denk ik ook helpen in het bewijs.
3. Als je één groot consecutive blok hebt van birdlocations en het grootste explosief is
groter dan
n, laten we zeggen
e groter en alle andere explosieven nog wel kleiner dan n. Dan moet je bewijzen dat je nog steeds een waarde tussen
X-1-e en
X-1 kunt construeren. Je kunt dit
waarschijnlijk benaderen door twee situaties te bekijken:
X > n en
X < n.
Vervolgens heb je de case nog van meerdere blokken (
2 tot
n-1) van birdlocations. Als je bovenstaande hebt bewezen, kun je kijken hoe je dit kunt gebruiken om het te bewijzen voor twee consecutive blokken. Het verhaal zal grotendeels hetzelfde zijn en je kunt dus gebruiken dat ze beiden kleiner zijn dan
n-1, zelfs als de ene
a lang is, dan is de ander
n-1-a lang. Als dit allemaal lukt, heb je volgens mij de twee stappen die nodig zijn voor een proof by induction en kun je dit dus generaliseren.
Exact proberen dit allemaal te bewijzen, heb ik persoonlijk niet zo'n zin in ^^ Dus hopelijk heb je iets aan hoe ik het bekeken heb, want meestal helpt het wel om dit soort problemen een beetje de bespreken en dan vallen er ineens kwartjes
Qua hoe het te programmeren,
gok ik dat de crux hem dus zit in het samenstellen van de verschillende
X-en als het ware. Hoe hier precies de recursie bij komt kijken waar ze het over hebben in de opdracht, zie ik nog niet zozeer. De enige recursieve manier die ik voor ogen heb, is namelijk gewoon de boel zowat bruteforcen.
Tot slot nog de nodige disclaimer dat wat ik hierboven zeg allemaal een beetje uit de losse pols is en ik dus geen idee heb of dit werkelijk een oplossing brengt. Daarbij had je natuurlijk al veel eerder aan de bel moeten trekken bij leraren/assistenten. Ik neem tenminste aan dat je hier wel langer dan een dag voor hebt gehad
