|
|
|
•wefgef
|
 |
« Răspunde #1 : Decembrie 10, 2013, 18:21:33 » |
|
Pe fiecare linie/coloana poti gasi ordinea relativa a elementelor. Intre oricare doua elemente conscutive (considerand ordinea lor relativa, nu pozitiile) de pe o linie/coloana tragi muchie. Sortezi topologic graful.
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #2 : Decembrie 10, 2013, 23:46:16 » |
|
Tare solutia. Dar nu inteleg de ce punem muchii doar intre elementele consecutive. De exemplu daca pe o linie elementele au ordinea 2 1 3, cum se stabileste ordinea intre 2 si 3?
|
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #3 : Decembrie 11, 2013, 13:36:09 » |
|
Cand tragi muchiile iei in considerare ordinea relativa a elementelor, nu pozitiile lor. Pentru exemplul dat de tine, vom trage muchiile 2->1 si 1->3.
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #4 : Decembrie 11, 2013, 14:17:12 » |
|
Mersi, am inteles. Credeam ca se iau doar elementele adiacente in matrice.  |
|
|
|
|
Memorat
|
|
|
|
|
•vladtarniceru
|
|
« Răspunde #5 : Decembrie 11, 2013, 15:46:07 » |
|
Am incercat-o si eu ieri, si iau TLE 12 sau ceva de genul.. ce complexitate ati scos?
Eu am gasit in O(x log n + x), unde x este numarul de elemente din matrice (x = n * n), iar log-ul e de la calcularea ordinii elementelor pe linie / coloana (nu dau spoilere, cu toate ca e destul de simplu). Se poate totusi calcula in O(x) ordinea?
|
|
|
|
|
Memorat
|
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #6 : Decembrie 12, 2013, 22:22:38 » |
|
Mi-a iesit cu complexitatea ta.
|
|
|
|
|
Memorat
|
|
|
|
|
•popoiu.george
|
|
« Răspunde #7 : Decembrie 12, 2013, 23:12:35 » |
|
Eu tot iau WA pe testul 21, vad ca tu ai luat pe 24. Ce-ai facut sa scapi de WA?
|
|
|
|
|
Memorat
|
|
|
|
|
•wefgef
|
|
« Răspunde #8 : Decembrie 13, 2013, 00:31:05 » |
|
Da, se poate sorta liniar fiecare linie/coloana. Complexitatea ceruta este O(N^2).
|
|
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
|
•PlayLikeNeverB4
|
|
« Răspunde #9 : Decembrie 13, 2013, 17:56:04 » |
|
WA e probabil de la cazul in care nu exista solutie. Trebuie sa verifici daca graful e conex si aciclic. Posibil si sa verifici daca matricele sunt corecte, dar nu stiu exista un astfel de test.
Cum se sorteaza liniar? Nu ma prind.
|
|
|
|
|
Memorat
|
|
|
|
|
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena