GMOT
Nieuws:
 
*
Welkom, Gast. Alsjeblieft inloggen of registreren.
De activerings e-mail gemist?
12 December 2017, 07:11:00


Login met gebruikersnaam, wachtwoord en sessielengte


Pagina's: [1]
  Print  
Advertenties


the thriforce
Pretty addicted
*******

Berichten: 2.929



Bekijk profiel WWW
« Gepost op: 13 Oktober 2015, 01:09:57 »

Voor school moet ik een programmaatje schrijven dat met input voor een soort probleem daar een oplossing voor bedenkt. 't Probleem is alleen dat ze bedacht hebben dat het niet met bruteforce mag en nu snap ik er de ballen van. Een tipje die ze geven is dat als je kan bewijzen dat er altijd een oplossing is dat je dit bewijs dan om kan zetten naar een programma. Ik heb echter geen flauw idee hoe en het moet toch echt morgen ingeleverd dus ik hoop dat er bij iemand hier misschien wel een lampje gaat branden en mij even de goede richting in kan helpen.

Dit is ook echt niet als zo'n 'hè jongens maak mijn huiswerk'-vraag bedoelt maar meer als een 'ik heb geen idee wat ik moet doen kan iemand me op weg helpen'-vraag.

Het probleem
Spoiler:
Explosive Recursion

Introduction

The government has decided that it's about time we sent something into space again. However due to the recent economic recession there's a rather tight budget for this. Luckily the government still has an old shed full with explosives lying around which they can use to get to space. There are some problems though with the launch site. Some of the heights are habited by rare protected bird species. The rocket is allowed to fly through these but is not allowed to detonate explosions at these specific locations.

The bird protection people have numbers on on what heights the birds reside, and the space agency has numbers on how far each explosive will take the rocket in kilometres. There are no two explosives that make the rocket travel the same distance. The space agency doesn't have a budget to hire someone to do the calculating, so you volunteered to help them get their rocket's to space because you're a nice guy.

The rocket uses explosives tied to the bottom to propel them upward. This means that you can't stop them once you lighted them, and they will always travel a set distance. (The space agency has made budget cuts, and decided a lot of money could be saved if they ignored gravity and friction). This set distance is a integer given to you, and will always be a round natural number. No multiple explosives can be fired since that would damage the rocket and bring the astronaut in danger. The bird federation also gives you these numbers as round numbers. There's always one less bird spot then there are explosives.

It is your task to figure out in what order to ignite the explosives in such a way that you do not blow up any rare birds.

Exercise

The input is a positive integer N, followed by N positive integers. Each of these are the number of meters the i-th explosive will take you. Then there are N-1 positive integers which are the heights at which rare birds reside and no explosive should be ignited. Both of these are in kilometres.

The output are N integers, the zero-based indices of the explosives to ignite (The first explosive on the list is indexed 0). The order of the output is the order in which to ignite them. This order is such that no explosive will be ignited on a bird spot and all explosives are ignited.

The rocket starts at height 0, and the target destination is at the location you get to after igniting all the explosives. There are no rare birds at either the starting position 0 or the maximum position. They are all between these two positions.

It is in fact always possible to get the rocket to maximum height, no matter the locations of the birds or the distance each explosive propels you. Not just in the test cases I give you but for all input you can generate given the restrictions. Your program should essentially be a proof of this fact. This is a really important given property if you want to solve the program effectively. On igniting a explosive, the rocket always fly exactly the number of kilometres given in the input for that explosive. You cannot decide to fly a shorter distance than that. Also note that the number of kilometres a explosive can take you is different for every explosive.

Hint: use recursion. You could change your recursion to a non-recursive program later (to prevent a stack overflow for really large inputs). In your recursion, remember that it's also possible to recurse and change the result of that recursive call after the recursion.

Constraints

You have to do better than simply trying all possible orders of igniting the explosives (brute-forcing). This would take way too long. You have to at least be able to calculate an ordering for 100 explosives, for any input of that size. You should try to make a program that directly constructs a good ordering. Any approach involving trying lots of ways hoping to stumble on a good ordering will be too slow. A good place to start is to try to prove that there is always a good ordering, and then converting that proof into a program. Figuring the problem out by paper before programming it will help you.

If your program is too slow for any input with 100 explosives your solution is no good. Too slow means that it takes you more then a few seconds to solve for 100 explosives. You'll notice.

Examples

Some example inputs. If the second case takes long you're on the wrong track with your algorithm. Do note that for some inputs there can be multiple solutions but Peach only checks for one, so don't panic if Peach says you got it wrong but have a look at the in and output. And as always, do your own tests to make sure it works, Peach is just there to help you test.

input (split to three lines for clarity)

3
2 4 6
4 8


output

0 1 2

a different output

2 1 0

input (split to three lines for clarity)

20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191


output

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0


Ik heb nu zelf 3 gevallen bedacht waarin je zeker weet dat een bom goed is maar die gevallen zijn helaas niet volledig dekkend.

  • De laatste bom is altijd goed.
  • Als je voorbij alle vogels bent zijn alle bommen goed.
  • Als een bom over een vogel heen gaat en weer op een leeg plekje terecht komt is dit ook altijd goed omdat je dan in principe opnieuw in een vergelijkbare situatie komt maar dan met een n die 1 lager is.

Het probleem is dus vooral dat ik niet weet wat ik moet doen als je nog niet alle vogels voorbij bent maar geen bom hebt die er overheen kan. Sowieso weet ik ook niet of op deze manier naar het probleem kijken wel de juiste manier is.
Gelogd

ericlegomeer
King of the hill
******

Berichten: 1.660


http://xkcd.com/386/


Bekijk profiel
« Antwoord #1 Gepost op: 13 Oktober 2015, 11:08:13 »

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 Smiley

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 Wink
Gelogd



the thriforce
Pretty addicted
*******

Berichten: 2.929



Bekijk profiel WWW
« Antwoord #2 Gepost op: 13 Oktober 2015, 15:34:16 »

Ik heb uiteindelijk nog een geval toegevoegd voor als het aantal bommen over - het aantal vogels voor je groter dan 1 is omdat je dan elke bom die niet op een vogel uitkomt mag gebruiken.

Daarna gaat het programma bruteforcen.

Verder heb ik ook nog de bommen gesorteerd zodat hoge verplaatsingen als laatste gebruikt worden bij het bruteforcen omdat deze vaker later nog nodig zijn om over een grotere groep vogels heen te komen.

Uiteindelijk doet hij de tests van de inleversite allemaal nog redelijk snel. (De test die echt bedoelt is om naar je performance te kijken met 100 bommen doet hij in 0.24 sec.)

Verder had ik hier inderdaad langer dan een dag voor ik had namelijk iets minder dan een week. Echter is dit voor het zogeheten 'Challenge Program' van mijn vak programming wat extra opdrachten zijn voor studenten die al enigszins kunnen programmeren en daar is eigenlijk niet echt enige vorm van begeleiding voor. Alle contacturen die we hebben zijn gericht op het normale programma.

Verder denk ik dat ze ons ook wel wat overschat hebben met deze opdracht, want ik zit in een groepsgesprek met 100 mensen van mijn studie waarvan er naar mijn schatting zo'n 40 mensen het challenge program doen en daarvan snappen maar 2 mensen hoe het moet zonder bruteforcing.
Gelogd

djekkoo
Pretty addicted
*******

Berichten: 4.505


Bekijk profiel
« Antwoord #3 Gepost op: 13 Oktober 2015, 18:14:40 »

Kun je niet gewoon berekenen op welke plekken je welke bommen allemaal mag gebruiken, zodat je niet stil gaat staan op de plek van een vogel. Om daarna een semi-bruteforce techniek te gaan gebruiken om te bepalen welke je ook daadwerkelijk op welke plek af wilt vuren? (Misschien dat je die gegevens ook nog in een soort pathfinding algorithme kunt proppen, maar daar heb ik niet lang genoeg over nagedacht. Tongue)
Gelogd

Je hebt het recht brutaal te zijn, op voorwaarde dat je weet waarover je spreekt - Goethe

Suwranna
Look mum, I can post!
*

Berichten: 2


Bekijk profiel
« Antwoord #4 Gepost op: 16 Oktober 2017, 07:48:14 »

Het is meer voorkomend dat de bevolking meer arbeid vraagt. Kennis is een belangrijke vertaling voor werkaanvraag.
Gelogd

sasbom
Pretty addicted
*******

Berichten: 2.963


Frenchformers, bistro's in disguise


Bekijk profiel
« Antwoord #5 Gepost op: 17 Oktober 2017, 18:40:26 »

Het is meer voorkomend dat de bevolking meer arbeid vraagt. Kennis is een belangrijke vertaling voor werkaanvraag.

jep ik ben het eens met je.
Economie belasting is fundamenteel voor het mortuariumregister van het nieuwsmoment
Gelogd

-=hardcore 3dsmax'er, maya'er, zbrusher, after effects'er, photoshop'er en gamemakerer=-
I sexually identify as a tomato
Ontdek je karma met shoarma

*kaas1 & sasbom zingen het www.webet.tk lied*
- Nickienator


Advertenties
Pagina's: [1]
  Print  

 
Ga naar:  

Powered by SMF 1.1.21 | SMF © 2006-2011, Simple Machines | Smartphoneversie bekijken

Dilber MC Theme by HarzeM