Forum » Programiranje » [izziv] volilna območja
[izziv] volilna območja
Yacked2 ::
Pozdravljeni,
odpiram temo za pogovor o izzivu, ki ga je v sklopu ACM srednješolskega tekmovanja postavil IJS. Naloga z celotnim opisom se nahaja na: http://rtk.ijs.si/2016/gerry/
Rok za oddajo rešitev je: 18. marec 2016
Če besedilo naloge malo skrajšam, podan je pravokotnik, ki ga je potrebno razdeliti na k-delov (celice se morajo držati skupaj po stranici) tako, da je razlika vsot polj posameznih delov najmanjši. Maksimalna velikost pravokotnika je 300 x 300.
Sicer sem malo prestar za sodelovanje, ampak vseeno:
Sam sem prišel do ideje, bi se sprehodil čez vse možnosti in vrnil najboljšo, a na žalost nikjer ni objavlen dovoljen čas, ki ga ima algoritem za izvajanje. Ali pa bi naključno zgeneriral 1000 različnih razrezov in vrnil najboljšega.
Ima kdo boljšo idejo ?
lp
Yacked2
odpiram temo za pogovor o izzivu, ki ga je v sklopu ACM srednješolskega tekmovanja postavil IJS. Naloga z celotnim opisom se nahaja na: http://rtk.ijs.si/2016/gerry/
Rok za oddajo rešitev je: 18. marec 2016
Če besedilo naloge malo skrajšam, podan je pravokotnik, ki ga je potrebno razdeliti na k-delov (celice se morajo držati skupaj po stranici) tako, da je razlika vsot polj posameznih delov najmanjši. Maksimalna velikost pravokotnika je 300 x 300.
Sicer sem malo prestar za sodelovanje, ampak vseeno:
Sam sem prišel do ideje, bi se sprehodil čez vse možnosti in vrnil najboljšo, a na žalost nikjer ni objavlen dovoljen čas, ki ga ima algoritem za izvajanje. Ali pa bi naključno zgeneriral 1000 različnih razrezov in vrnil najboljšega.
Ima kdo boljšo idejo ?
lp
Yacked2
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!
Randomness ::
a na žalost nikjer ni objavlen dovoljen čas, ki ga ima algoritem za izvajanjeČe prav razumem, znaša dovoljen čas nekaj več kot štiri mesece, merjeno v "wall clock" času. :-)
Drugače pa kar zanimiva naloga.
aaa1 ::
Zelo zanimiva naloga, samo se mi zdi da boš z uporabo brute force zaribal, sploh pri 300x300 mreži, kjer imaš preveč možnosti. Jaz bi malo razmislil, kako omejiti vse te možnosti... Naprimer, kaka je razlika med min in max vrednostmi. Na faksu smo imeli eno seminarsko, kjer je mogla kača sama po labirintu najti pot. To smo nardil tako, da si na sklad shranjeval trenutno pot, ko si se kje zaplezal oziroma ustavil, si se po skladu vračal nazaj, do neke točke in poskusil od tam naprej. Zdaj za brute force, bi jaz uporabil isto strategijo, samo da si izbereš najvišja št volilcev, samo tukaj potem se spet pojavi vprašanje, na koliko delov razdeliti celo območje... Mogoče pa obstaja kaka matematična teorija za elegantno rešitev. :) Kaj pri vrstah oziroma vsotah... Nevem my 2c.
Smurf ::
Jap, casa imas 4 mesece, optimizirati pa moras vseh tistih 1000 primerov. Ampak pomoje cisti bruteforce tukaj ne bo zmagal.
Se mi zdi, da bi se critticall kar dobro znasel pri taki nalogi.
edit: jaz bi verjetno zacel z merjenjem gostote in bi glede na to omejil velikosti v prvem koraku.
Se mi zdi, da bi se critticall kar dobro znasel pri taki nalogi.
edit: jaz bi verjetno zacel z merjenjem gostote in bi glede na to omejil velikosti v prvem koraku.
Zgodovina sprememb…
- spremenil: Smurf ()
krneki0001 ::
Če besedilo naloge malo skrajšam, podan je pravokotnik, ki ga je potrebno razdeliti na k-delov (celice se morajo držati skupaj po stranici) tako, da je razlika vsot polj posameznih delov najmanjši. Maksimalna velikost pravokotnika je 300 x 300.
Kakšne oblike morajo biti "poddeli"?
Če so lahko trikotniki, lahko to rešiš z delanoyevo triangulacijo ali pa voronojevim diagramom.
Ali pa z delanoyem narediš triangulacijo, potem pa najdaljše stranice iz delanoya umakneš z Urquhartovim grafom, pa dobiš skoraj same enake dele.
Zgodovina sprememb…
- spremenilo: krneki0001 ()
Yacked2 ::
U potem pa lahko sodelujem :)
Pravokotnik je sestavljen iz mreže kvadratov, kjer ima vsak kvadrat svojo vrednost, tako da moraš razdeliti na oglato telo, kjer se vsi deli držijo po stranici skupaj. Sem si pogledal delanoyevo triangulacijo vendar mislim da to ne bo rešitev. Naloga je pomojem zasnovana tako, da ne obstaja algoritem za optimalno razporeditev, saj v navodilih piše da se bo v primeru večih enako učinkovitih rešitev točke razdeljevalo drugače.
Sedaj sem prišel do sklepa, da bi bilo pametno že med branjem polj seštevati in nakoncu deliti s številom željenih območij, da veš koliko ljudi bo v posameznem območju. Težavo mi dela to, da so obtežena polja in ne povezave, sem poiskusil narediti digraf, vendar se potem zakomplicira računanje, ker na enkrat zrušim dve povezavi, se pravi, da eno vrednost mejnega polje izgubim.
Pravokotnik je sestavljen iz mreže kvadratov, kjer ima vsak kvadrat svojo vrednost, tako da moraš razdeliti na oglato telo, kjer se vsi deli držijo po stranici skupaj. Sem si pogledal delanoyevo triangulacijo vendar mislim da to ne bo rešitev. Naloga je pomojem zasnovana tako, da ne obstaja algoritem za optimalno razporeditev, saj v navodilih piše da se bo v primeru večih enako učinkovitih rešitev točke razdeljevalo drugače.
Sedaj sem prišel do sklepa, da bi bilo pametno že med branjem polj seštevati in nakoncu deliti s številom željenih območij, da veš koliko ljudi bo v posameznem območju. Težavo mi dela to, da so obtežena polja in ne povezave, sem poiskusil narediti digraf, vendar se potem zakomplicira računanje, ker na enkrat zrušim dve povezavi, se pravi, da eno vrednost mejnega polje izgubim.
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!
::
Jaz bi se lotiv tako da bi si naredo objekte za polja in objekte za povezave med poljami.
Vsako polje ima lahko poljubno povezav na druga polja (v začetku ne več kot 4 pozneje pa ko polja združuješ v kompleksnejše oblike pa je lahko povezav več).
Problem bi nato se lotil reševati v zanki katera se ponovi tolikokrat da dosežeš želeno število volilnih območi. Zdaj ker je cil naloge dobiti čimbolje enaka območja in je mogoče samo združevanje bi poiskal tiste povezave katere polja najbol odstopajo od celice z največjo vrednost. Odnosno bi združil tista dva polja katera najbolj kvarita rezultat. Zraven bi popraviv seznam s polji in seznam s povezavami (kako zbrisal in dodal kako novo - s tem delom imam zaenkrat težave)
Ko bi to delovali pa bi videl kakšni so kaj rezultati in v primeru da niso optimalni bi poskušal še kaj drugega mogoče kje narediti fork in delati po kakšni drugi poti nevem.
Vsako polje ima lahko poljubno povezav na druga polja (v začetku ne več kot 4 pozneje pa ko polja združuješ v kompleksnejše oblike pa je lahko povezav več).
Problem bi nato se lotil reševati v zanki katera se ponovi tolikokrat da dosežeš želeno število volilnih območi. Zdaj ker je cil naloge dobiti čimbolje enaka območja in je mogoče samo združevanje bi poiskal tiste povezave katere polja najbol odstopajo od celice z največjo vrednost. Odnosno bi združil tista dva polja katera najbolj kvarita rezultat. Zraven bi popraviv seznam s polji in seznam s povezavami (kako zbrisal in dodal kako novo - s tem delom imam zaenkrat težave)
Ko bi to delovali pa bi videl kakšni so kaj rezultati in v primeru da niso optimalni bi poskušal še kaj drugega mogoče kje narediti fork in delati po kakšni drugi poti nevem.
Yacked2 ::
je izjavil:
Se popravlam: zgornje bi se verjetno zaplezalo v kakšno neoptimalno rešitev.
Se mi zdi ja
Verjetno je Smurfov predlog najboljši: že med branjem bi določal kje so kritična gorišča gostote v mreži, očitno bodo to centri razdelitev, nato pa random malo prestavljam mejo med posameznimi žarišči in najboljšo izpišem. Korak naprej ni vedno ustrezen...sploh če si na robu prepada!
W3by ::
Tudi meni je bil izziv zanimiv, zato sem se ga lotil ter za test že oddal nekaj primerov.
Sem pa uporabil super-optimized brute-force pristop (v C++). Beat me if you can.
Danes bom pognal na serverju (Xeon D)...
Sem pa uporabil super-optimized brute-force pristop (v C++). Beat me if you can.
Danes bom pognal na serverju (Xeon D)...
Red_Mamba ::
sj lahko tudi tukaj naredimo kdo pride do najboljse resitve :)
[st.slika https://img.shields.io/badge/Slo-Tech-green.svg test]
Linkedin >> http://goo.gl/839Aua
Mamba's Crypto & ICO's: https://t.me/joinchat/AAAAAExTkO4P4UDy0fIZdg
Linkedin >> http://goo.gl/839Aua
Mamba's Crypto & ICO's: https://t.me/joinchat/AAAAAExTkO4P4UDy0fIZdg
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Tristrane POKOČNE PRIZMEOddelek: Šola | 2192 (1744) | Bikica195 |
| » | Matematični problemOddelek: Šola | 1720 (1239) | BCSman |
| » | [Java] KonstruktorjiOddelek: Programiranje | 2128 (1980) | ta_pravi |
| » | mat naloga (kvadr. funkcija)Oddelek: Šola | 1794 (1580) | sherman |
| » | Kako kondenzatorju določt + in -Oddelek: Pomoč in nasveti | 1880 (1746) | HardwareMaster |