[GPC] Opgave 2 ** teruggetrokken **

[D2k]

Op dinsdag 04 december 2001 15:47 schreef LuCarD het volgende:

[..]

Is de 6 uur al voorbij

we hebben niet binnen 6 uur een nieuwe
we melden minimaal 6 uur van te voren

[Theswitch]

Op dinsdag 04 december 2001 15:41 schreef D2k het volgende:

[..]

als je wat inlevert krijg je punten (+ en - )
maar opgaven zijn nooit weg natuurlijk tnx

Net weer 1'tje, volgens mij moet er wel een leuke bijzitten. Als je ze niet gebruikt plaats ik ze hier wel vor de liefhebbers (De laatste lijkt me zelf ook wel leuk om te proggen, puzzel #4)

[D2k]

Op dinsdag 04 december 2001 15:56 schreef Theswitch het volgende:

[..]

Net weer 1'tje, volgens mij moet er wel een leuke bijzitten. Als je ze niet gebruikt plaats ik ze hier wel vor de liefhebbers (De laatste lijkt me zelf ook wel leuk om te proggen, puzzel #4)

als de GPC klaar is mag je van mij alles publiceren
ut zijn jouw opgaven wat mij betreft

[Theswitch]

Op dinsdag 04 december 2001 15:58 schreef D2k het volgende:

[..]

als de GPC klaar is mag je van mij alles publiceren
ut zijn jouw opgaven wat mij betreft

Ik wacht in spanning op een emailtje van jullie wat je er van vind en of er 1 in aanmerking komt.. ..

[Nielsz]

Had ik er eindelijk eentje in mijn hoofd met een paar leuke algoritmes erachter

_{D2k check cf}

[tomato]

Theswitch: Net weer 1'tje, volgens mij moet er wel een leuke bijzitten. Als je ze niet gebruikt plaats ik ze hier wel vor de liefhebbers (De laatste lijkt me zelf ook wel leuk om te proggen, puzzel #4)

Hoe kom je aan de puzzels? Heb je ze net zelf bedacht of zijn het reeds bestaande (met de kans dat enkele tweakers ze al kennen natuurlijk)?

[wasigh]

Okay we hebben een nieuwe opdracht. We moeten hem alleen nog uitwerken.

Je kunt hem verwachten:
<hr>
Morgen om ongeveer 10:00 (ja 's morgens)
<hr>
Bedankt dat jullie nog vertrouwen in ons hebben

We hebben ook een nieuw jurylid: Gerco

moet ik mijn l33t html skills weer gebruiken? of is dit duidelijk genoeg

[Theswitch]

Op dinsdag 04 december 2001 16:02 schreef tomato het volgende:

[..]

Hoe kom je aan de puzzels? Heb je ze net zelf bedacht of zijn het reeds bestaande (met de kans dat enkele tweakers ze al kennen natuurlijk)?

Zelf bedacht eigenlijk, en een beetje van 1e jaars opdrachten voor informatica studenten, die nog niet zo heel lastig zijn. Alle puzzels die ik bedacht heb en niet hier langskomen zal ik na de contest wel elke week posten.

[wasigh]

Op dinsdag 04 december 2001 16:08 schreef Theswitch het volgende:

[..]

Zelf bedacht eigenlijk, en een beetje van 1e jaars opdrachten voor informatica studenten, die nog niet zo heel lastig zijn. Alle puzzels die ik bedacht heb en niet hier langskomen zal ik na de contest wel elke week posten.

Of we kunnen ze gebruiken voor een volgende contest?

[Theswitch]

Op dinsdag 04 december 2001 16:09 schreef wasigh het volgende:

[..]

Of we kunnen ze gebruiken voor een volgende contest?

Jah dat mag ook natuurlijk, dan zal ik ze niet posten en verzin ik wel nieuwe tegen die tijd.

[Jerry]

Op dinsdag 04 december 2001 16:07 schreef wasigh het volgende:
moet ik mijn l33t html skills weer gebruiken? of is dit duidelijk genoeg

L33T HTML skills gebruiken plz

[wasigh]

Op dinsdag 04 december 2001 16:22 schreef Mr_UnAnimouS het volgende:

[..]

L33T HTML skills gebruiken plz

Ik heb mijn l33t mod powers gebruikt en er een sticky van gemaakt

[Verwijderd]

code:

8
16 3
83 7
30 30
66 44
72 68
36 81
84 86
5 90

de oplossing is volgens mij 55 52.

[wasigh]

we hebben een nieuwe e-mail adres, eentje die meer als 2 mb aankan: (bedankt Gerco)

[e-mail]

[Unicron]

ik vind het erg jammer dat de opdracht is teruggetrokken. Alleen maar omdat sommige mensen de opdracht niet snappen, terwijl het mij gewoon logisch lijkt wat bedoeld wordt.

[D2k]

http://www.dusty.nl/got

en link naar de opgaven en regelementen

tnx 2 dusty

[tomato]

Ik heb nog even gekeken naar deze opgave (beide varianten) en wanneer op de volgende manier geformuleerd vind ik hem nog erg interessant:

Uitgaande van de originele opdracht. Twijfel over wat de optimale locatie is voor het ziekenhuis wordt opgelost door de volgende doelstelling:

Vind een locatie voor het ziekenhuis, waarbij de maximale afstand tussen een huis en het ziekenhuis zo klein mogelijk is.

Het maximum aantal huizen moet wellicht iets teruggebracht worden (2 miljoen lijkt me voor deze opdracht bijna ondoenlijk).

Ik heb zelf al een paar leuke ideetjes, maar ben zeer benieuwd naar de slimmerik die dit snel op weet te lossen. Ik heb tot nu toe slechts enkele algoritmen in mijn hoofd voor verschillende situaties (en zonder dat je die situaties weet te identificeren kun je daar in je programma natuurlijk niets mee).

Dus, wie waagt?

[Twilight Burn]

Ik heb hem opgelost als "Vind de locatie voor het ziekenhuis zodat de gemiddelde afstand van de huizen naar het ziekenhuis zo KLEIN mogelijk is."
Ook kan het ziekenhuis nooit op een huis liggen

Die van 8:
55,52 = 328,03318188885
00:00:00.0100394
Oeps - klein foutje in men algoritme, hijs nu ook 2x zo snel bij deze opgave
2 miljoen kan die ook, maar dan duurt het minstens 8 seconden voordat ie de ideale plek heeft gevonden

[Verwijderd]

Op dinsdag 04 december 2001 19:58 schreef tomato het volgende:
Ik heb nog even gekeken naar deze opgave (beide varianten) en wanneer op de volgende manier geformuleerd vind ik hem nog erg interessant:
[..]

Ik heb zelf al een paar leuke ideetjes, maar ben zeer benieuwd naar de slimmerik die dit snel op weet te lossen. Ik heb tot nu toe slechts enkele algoritmen in mijn hoofd voor verschillende situaties (en zonder dat je die situaties weet te identificeren kun je daar in je programma natuurlijk niets mee).

Dus, wie waagt?

Ik heb het wat te druk om hier tijd in te gaan steken, maar ik heb wel een tip voor diegenen die het wel gaan doen:

Bereken eerst de convex hull (zoek maar op) van de punten. Dit kan in principe in O(n log n) tijd, maar dan moet je alle punten opslaan. Het kan ook in O(n^2) tijd en dan hoef je de punten niet op te slaan. Vervolgens hoef je alleen nog maar een punt te zoeken waarvoor de maximale afstand tot een punt OP DE CONVEX HULL minimaal is. Dit scheelt iig een enorme berg rekenwerk.

[tomato]

Twilight Burn: Ik heb hem opgelost als "Vind de locatie voor het ziekenhuis zodat de gemiddelde afstand van de huizen naar het ziekenhuis zo KLEIN mogelijk is."
Ook kan het ziekenhuis nooit op een huis liggen

Wat vind je bij:

code:

6
0 0
1 0
2 0
3 0
4 0
100 0

?

[Twilight Burn]

3,-1 = 106,231927264637
00:00:00.2108274

[tomato]

Twilight Burn: 3,-1 = 106,231927264637
00:00:00.2108274

Vergelijk dat eens met de gemiddelde afstand als je het ziekenhuis op 4 0 zou plaatsen.

[tomato]

Maar eigenlijk vind ik die met de zo kort mogelijke maximale afstand leuker, ik ga eens kijken naar de tips die Xalista gaf

[Nikel]

Ik had inderdaad een algoritme bedacht om de convex hull te bepalen zonder de punten op te hoeven slaan eerst. Leuk om te zien dat ik uit mezelf (en met behulp van een paar huisgenoten) dus inderdaad het juiste idee had. Als eenmaal de convex hull gevonden is het volgende te doen. Je zet het ziekenhuis ergens neer en kijkt of je de maximale afstand tot een huis kunt verkleinen door een van de 8 richtingen op te lopen. En zo verder tot het geen zin meer heeft het ziekenhuis te verplaatsen.

Mijn algoritme voor het bepalen van de convex hull vindt ik zelf erg mooi, maar het algortime om daarna de positie te bepalen moet beter kunnen.

Een idee is om van alle mogelijke driehoeken uit de convex hull een cirkel te maken waarvan de punten van die driehoek op de cirkel liggen. De grootste van deze cirkels moet volgens mij de cirkel zijn die je zoekt, maar of deze methode sneller is dan de eerder genoemde manier betwijfel ik sterk.

[Twilight Burn]

Op dinsdag 04 december 2001 20:36 schreef tomato het volgende:

[..]

Vergelijk dat eens met de gemiddelde afstand als je het ziekenhuis op 4 0 zou plaatsen.

Ik heb mijn programma iets aangepast, het laat nu ook de minimale afstand zien als hij op een huis zou staan:

code:

Normal:   3,-1: 106,231927264637
On house: 3,0: 104
00:00:00

[Verwijderd]

Mijn oplossing, die al af is maar in de optimalisatiefase zit (al is dat nu niet meer nodig), werkt met behulp van het line-algorithm dat Bresenhem ooit bedacht om lijnen te tekenen op een monitor. Alleen resulteerde het algo van Bresenhem in de coordinaten van de pixels (de lokaties op de map in dit geval) en was ik in deze opgave alleen geinteresseerd in de afstand tussen 2 punten. Supersimpel. Even de totalen optellen en de min. is de optimale positie.. De eventuele optimalitie zit in het aantal punten dat je test op mogelijke posities voor het ziekenhuis(kandidaten), daar ben/was ik nog mee bezig.

[Theswitch]

* Theswitch kijkt op 'z horloge... 10.00

[Crysania]

10:01 al

komt er een nieuw topic of komt het in deze??

[Wokker]

Op woensdag 05 december 2001 10:01 schreef THE_CR0SS het volgende:
10:01 al

Journaal is ook al afgelopen !!
KOm maar op met die contest

[wasigh]

omstreeks 10:00
(mijn bed had wat vertraging vanochtend en de rest van de jury moet de opgave nog goedkeuren..)

[Crysania]

volgens mij zitten er best veel mensen hier de hele tijd op F5 te douwen tot er een nieuw topic is

[Crysania]

Op woensdag 05 december 2001 10:02 schreef wasigh het volgende:
omstreeks 10:00
(mijn bed had wat vertraging vanochtend en de rest van de jury moet de opgave nog goedkeuren..)

NS-wanabee

[D2k]

Op woensdag 05 december 2001 10:02 schreef wasigh het volgende:
omstreeks 10:00
(mijn bed had wat vertraging vanochtend en de rest van de jury moet de opgave nog goedkeuren..)

rotflol

mwoah dat goedkeuren moet idd iets zorgvuldiger dan de vorige keer

[Verwijderd]

Op woensdag 05 december 2001 10:03 schreef THE_CR0SS het volgende:
volgens mij zitten er best veel mensen hier de hele tijd op F5 te douwen tot er een nieuw topic is

[wasigh]

hij is in ieder geval door 1 jurylid nu goedgekeurd (d2k waar blijf je???)

[D2k]

Op woensdag 05 december 2001 10:15 schreef wasigh het volgende:
hij is in ieder geval door 1 jurylid nu goedgekeurd (d2k waar blijf je???)

zie geen mail????????

gevonden
zal um ff bekijken
moment

[Crysania]

krijg een lamme vinger van de F5

[drm]

volgende keer een absolute fout berekenen bij de tijd die je vertelt

[Verwijderd]

Hee, het is 10:00!!!

[wasigh]

momentje nog..

[Verwijderd]

Bij mij is het al kwart over 10 hoor

[Crysania]

er staat trouwens nergens omstreeks 10:00 !!!

ik wil opgave!!!

[wasigh]

ok hij is nu door 2 jury leden goedgekeurd.
Hou het oude sticky topic in de de gaten...

[Theswitch]

M'n #!/usr/bin/perl
in de editor staat al klaar

hmm. dit is wel een erg foute manier.. eerst een design/ontwerp maken, dan pas implementeren.. nah, wtf, proggen is leuker

[Verwijderd]

Op woensdag 05 december 2001 10:22 schreef Theswitch het volgende:
hmm. dit is wel een erg foute manier.. eerst een design/ontwerp maken, dan pas implementeren.. nah, wtf, proggen is leuker

En wat is daar fout aan ik begin ook altijd meteen en ik heb opgave 1 ook nog opgelost dus

[D2k]

psssssssssssssssssssst

[topic=340659/1/25]