Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Lian Yu  (Citit de 2323 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
freak93
Echipa infoarena
Nu mai tace
*****

Karma: 341
Deconectat Deconectat

Mesaje: 804



Vezi Profilul
« : Martie 26, 2016, 08:58:32 »

Aici se pot pune întrebări legate de problema Lian Yu de la concursului AGM 2016.
Memorat
staucavulturulpestanca
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #1 : Martie 26, 2016, 10:11:55 »

restrictia "Intre oricare doua asezari exista maxim un drum" inseamna ca graful nu contine muchii duble, sau ca este aciclic?
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #2 : Martie 26, 2016, 10:16:04 »

restrictia "Intre oricare doua asezari exista maxim un drum" inseamna ca graful nu contine muchii duble, sau ca este aciclic?

In enunt, drumurile au semnificatia legaturilor directe intre doua asezari.
Memorat
CNDG_Oncescu_Binica_Sitaru
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 3



Vezi Profilul
« Răspunde #3 : Martie 26, 2016, 11:07:45 »

Pentru ca mercenarii sa se stranga intr-un nod, trebuie sa poate ajunge pe drumurile existente, sau se considera ca se teleporteaza sau ceva de genu?
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #4 : Martie 26, 2016, 11:19:44 »

Citat
Pentru ca mercenarii sa se stranga intr-un nod, trebuie sa poate ajunge pe drumurile existente, sau se considera ca se teleporteaza sau ceva de genu?
"Se poate ajunge de la oricare asezare la oricare alta mergand pe cele M drumuri", deci ei tot timpul o sa poata ajunge in orice nod (poti sa consideri ca se si teleporteaza daca vrei, e acelasi lucru Very Happy)
Memorat
tudormaxim
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #5 : Martie 26, 2016, 14:15:43 »

Citat
Intre oricare doua asezari exista maxim un drum
In exemplu exista 2 drumuri de la asezarea 1 la asezarea 4 (1 -> 2 -> 3 -> 4 si 1 -> 4). E gresit exemplul sau nu ma prind eu?
Memorat
AGMinformatica
De-al casei
***

Karma: 0
Deconectat Deconectat

Mesaje: 124



Vezi Profilul
« Răspunde #6 : Martie 26, 2016, 14:21:56 »

Citat
Intre oricare doua asezari exista maxim un drum
In exemplu exista 2 drumuri de la asezarea 1 la asezarea 4 (1 -> 2 -> 3 -> 4 si 1 -> 4). E gresit exemplul sau nu ma prind eu?

S-a mai raspuns la intrebarea asta, verifica mai sus
Memorat
tudormaxim
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 4



Vezi Profilul
« Răspunde #7 : Martie 26, 2016, 14:43:26 »

Acum am vazut. Multumesc.
Memorat
andrew_assassin789
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 5



Vezi Profilul
« Răspunde #8 : Martie 27, 2016, 17:51:36 »

Se pot da niste hinturi in legatura cu solutia?  Smile
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #9 : Martie 27, 2016, 20:24:54 »

Salut, sper că nu greșesc, fiindcă n-am implementat-o. În principiu îți faci arborele de componente biconexe și faci o dinamică pe el. Gândește în direcția asta.
Memorat
bciobanu
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #10 : Martie 31, 2016, 19:03:00 »

Există vreo restricție în problemă care face ca acest test (arborele linie pentru N și K maxime) să nu fie unul valid?
Memorat
xtreme77
Client obisnuit
**

Karma: 7
Deconectat Deconectat

Mesaje: 69



Vezi Profilul
« Răspunde #11 : Martie 31, 2016, 19:27:18 »

Există vreo restricție în problemă care face ca acest test (arborele linie pentru N și K maxime) să nu fie unul valid?

Aaah, care e mai exact problema ?  Confused
Memorat
bciobanu
Strain


Karma: 5
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #12 : Martie 31, 2016, 19:34:15 »

Aaah, care e mai exact problema ?  Confused

M-am gandit la o dinamica acum cateva zile, care merge bine in medie, dar pe testul acesta e O(N^3), iar azi am consultat sursele oficiale de pe github si ambele iau TLE (cam 60 de secunde cu -O2) pe acest test.
Memorat
george_stelian
Echipa infoarena
Strain
*****

Karma: 6
Deconectat Deconectat

Mesaje: 35



Vezi Profilul
« Răspunde #13 : Martie 31, 2016, 22:16:59 »

Aveam o eroare in sursa, dar aceasta nu a modificat cu nimic corectitudinea problemei sau testele. Cand o sa postam si solutiile o sa vezi de ce sursa are complexitate per total O(N*K+N*N) (o sa scriu si demonstratia matematica). Ne cerem mii de scuze. Am pus sursa corectata si pe GitHub.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines