Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: SGU 354. Just Matrix  (Citit de 13045 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« : Decembrie 09, 2013, 21:31:58 »

http://acm.sgu.ru/problem.php?contest=0&problem=354

Stie cineva cum se face problema asta ?  Smile

Nu am nici o idee, multumesc anticipat.
Memorat
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #4 : Decembrie 11, 2013, 14:17:12 »

Mersi, am inteles. Credeam ca se iau doar elementele adiacente in matrice.  d'oh!
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« Răspunde #6 : Decembrie 12, 2013, 22:22:38 »

Mi-a iesit cu complexitatea ta.
Memorat
popoiu.george
Vorbaret
****

Karma: 19
Deconectat Deconectat

Mesaje: 162



Vezi Profilul
« 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
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« 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
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 721



Vezi Profilul
« 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
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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