Titlul: Rama Scris de: Serban Andrei Stan din Martie 24, 2013, 00:56:58 Aici se pot pune întrebări legate de problema Rama de la Runda 4 a concursului Algoritmiada 2013.
Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII. Titlul: Răspuns: Rama Scris de: Craciun Catalin din Martie 24, 2013, 09:26:41 Scuzati-ma dar sunt nou pe infoarena... Sursele le salvam cu numele problemei?
Titlul: Răspuns: Rama Scris de: Adrian Budau din Martie 24, 2013, 09:36:38 Intrebarea puteai sa o pui chiar pe topicul concursului. http://www.infoarena.ro/forum/index.php?topic=8798.0 (http://www.infoarena.ro/forum/index.php?topic=8798.0).
Dar oricum ca sa-ti raspund la intrebare: NU, nu trebuie sa salvezi cu numele problemei. Trebuie doar sa ai extensia .cpp .c sau .pas . Titlul: Răspuns: Rama Scris de: Craciun Catalin din Martie 24, 2013, 09:39:47 Multumesc mult
Titlul: Răspuns: Rama Scris de: George Marcus din Martie 24, 2013, 10:15:55 Liniile formate din elemente de 1 se considera si ele valide?
Titlul: Răspuns: Rama Scris de: Ionescu Vlad din Martie 24, 2013, 10:17:24 Da, si liniile si coloanele!
Titlul: Răspuns: Rama Scris de: Darius-Florentin Neatu din Martie 24, 2013, 14:37:17 o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p... TLE pe 3 teste ...
eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col... apoi am sortat vectorul cu quicksort dupa val... si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)... si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)... sugestii de optimizare? Titlul: Răspuns: Rama Scris de: Popa Razvan din Martie 24, 2013, 15:53:34 Care era complexitatea oficiala ?
Titlul: Răspuns: Rama Scris de: Cosmin Negruseri din Martie 24, 2013, 16:02:21 n^2 log n dar s-a luat 100 cu n^3
Titlul: Răspuns: Rama Scris de: Popa Razvan din Martie 24, 2013, 16:14:31 n^2 log n dar s-a luat 100 cu n^3 Ciudat, eu am avut O(N^3) si am luat 60p. Un hint pentru O(N^2 * logN) ? Titlul: Răspuns: Rama Scris de: Gogu Marian din Martie 24, 2013, 16:16:32 Sunt curios de solutia N^2 log N, suna misto.
Eu chiar am presupus ca era limita pentru N^3, ca intra in timp, doar ca am avut un bug la sursa trimisa in concurs care nu s-a manifestat pe niciunul din testele open :D Titlul: Răspuns: Rama Scris de: Andretti Naiden din Martie 24, 2013, 19:51:22 o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p... TLE pe 3 teste ... eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col... apoi am sortat vectorul cu quicksort dupa val... si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)... si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)... sugestii de optimizare? Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare. Titlul: Răspuns: Rama Scris de: Adrian Budau din Martie 24, 2013, 19:55:14 Ca hint pentru N^2 log:
Divide et Impera Titlul: Răspuns: Rama Scris de: Darius-Florentin Neatu din Martie 25, 2013, 08:39:16 Citat Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare. mersi. incerc sa implementez ce mi-ai zis. revin cu rezultatul Titlul: Răspuns: Rama Scris de: Darius-Florentin Neatu din Martie 25, 2013, 09:54:56 o problema interesanta....insa nu m-am prins de rezolvarea de 100p....iau 70p... TLE pe 3 teste ... Poti retine pt fiecare element din matrice lungimea unei secvente de 1 care incepe cu el spre dreapta ,respectiv in jos.Te folosesti de asta in functia de verificare.eu am facut mai intai un vector v cu elemente record (val,lin,col) cu semnificatia val este aria dreptunghiului care are dimensiunile lin*col... apoi am sortat vectorul cu quicksort dupa val... si am pornit cu cea mai mare valoare v[k].val. daca gaseam un dreptunghi care sa aiba aria val ma opream daca nu treceam la urmatorul (k-1)... si la fiecare pas apelez o functie drept(x,y) cu semnificatia : cauta un dreptunghi de dimensiuni x*y..si imi verifica pentru fiecare dreptunghi x*y daca e bordat cu 1 (daca a gasit unul se opreste)... sugestii de optimizare? ideea sugerata de andretti am implementat-o prin procedurile spre_dreapta si in_jos (lungimile respective salvandu-le in matricele dr si jos ). Cod:
|