|
Titlul: SGU 354. Just Matrix Scris de: George Popoiu din Decembrie 09, 2013, 21:31:58 http://acm.sgu.ru/problem.php?contest=0&problem=354
Stie cineva cum se face problema asta ? :) Nu am nici o idee, multumesc anticipat. Titlul: Răspuns: SGU 354. Just Matrix Scris de: Andrei Grigorean din 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.
Titlul: Răspuns: SGU 354. Just Matrix Scris de: George Marcus din 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?
Titlul: Răspuns: SGU 354. Just Matrix Scris de: Andrei Grigorean din 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.
Titlul: Răspuns: SGU 354. Just Matrix Scris de: George Marcus din Decembrie 11, 2013, 14:17:12 Mersi, am inteles. Credeam ca se iau doar elementele adiacente in matrice. #-o
Titlul: Răspuns: SGU 354. Just Matrix Scris de: Vlad Tarniceru din 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? Titlul: Răspuns: SGU 354. Just Matrix Scris de: George Marcus din Decembrie 12, 2013, 22:22:38 Mi-a iesit cu complexitatea ta.
Titlul: Răspuns: SGU 354. Just Matrix Scris de: George Popoiu din 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?
Titlul: Răspuns: SGU 354. Just Matrix Scris de: Andrei Grigorean din Decembrie 13, 2013, 00:31:05 Da, se poate sorta liniar fiecare linie/coloana. Complexitatea ceruta este O(N^2).
Titlul: Răspuns: SGU 354. Just Matrix Scris de: George Marcus din 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. |