infoarena

Aici se pot pune întrebări legate de problema Lian Yu (http://www.infoarena.ro/problema/lianyu) de la concursului AGM 2016 (http://www.infoarena.ro/agm2016).

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.

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 :D)

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

Acum am vazut. Multumesc.

Se pot da niste hinturi in legatura cu solutia?  :)

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.

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

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.

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.