Lian Yu

[•freak93]

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

[•staucavulturulpestanca]

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

[•AGMinformatica]

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.

[•CNDG_Oncescu_Binica_Sitaru]

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?

[•AGMinformatica]

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 )

[•tudormaxim]

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?

[•AGMinformatica]

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

[•tudormaxim]

Acum am vazut. Multumesc.

[•andrew_assassin789]

Se pot da niste hinturi in legatura cu solutia? 

[•klamathix]

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.

[•bciobanu]

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

[•xtreme77]

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 ? 

[•bciobanu]

Aaah, care e mai exact problema ? 

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.

[•george_stelian]

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.