Titlul: 803 Secvmax Scris de: Andrei Grigorean din Februarie 15, 2009, 13:34:25 Aici puteti discuta despre problema Secvmax (http://infoarena.ro/problema/secvmax).
Titlul: Răspuns: 803 Secvmax Scris de: Radu Zernoveanu din Februarie 15, 2009, 19:22:33 Am luat 100 de puncte cu o solutie cu complexitatea O( N ^ 2 + M log N ) (JOB #259743). Consider ca ar trebui adaugat testul in care elementele sa fie: 1, 2, 3, ... 100.000 si sa fie grupat cu 2 - 3 alte teste ca sa se diferentieze solutia corecta de aceasta.
Titlul: Răspuns: 803 Secvmax Scris de: Gheorghe Cosmin din Februarie 15, 2009, 21:45:27 Asa e. Mie nu mi-a venit solutia asta si am dat testele destul de random. Asa ca un N^2 sa determini primul numar mai mare din stanga sau din dreapta merge destul de repede. O sa schimb cateva teste.
LE: Am schimbat doua teste si le-am grupat cu altele doua. Am dat reeval la sursele din arhiva de probleme. Unele surse iau mai putine puncte acum. Solutia N^2 cum face Radu ar trebui sa ia 60. Titlul: Răspuns: 803 Secvmax Scris de: Sima Cotizo din Februarie 19, 2009, 20:46:03 Revin cu rugamintea stearsa mai devreme: Puteti explica ceva mai clar solutia oficiala (macar un PM daca nu vreti sa stricati bucuria altora).
De exemplu, solutia lui Andrei mi se pare mai clara, dar nu inteleg bine ce face "stiva". Am crezut ca este vorba de un fel de vector ordonat ca la problema determinarii subsirului crescator maximal (cea de complexitate NlogN, nu stiu alta mai buna), dar oricum l-as intoarce nu gasesc o solutie buna. Titlul: Răspuns: 803 Secvmax Scris de: Gheorghe Cosmin din Februarie 19, 2009, 23:38:23 Am pus niste explicatii in plus la solutie. Sper sa se inteleaga acum :). Imi cer scuze pentru ambiguitate.
Solutia lui Andrei se foloseste de o stiva intiala pentru a determina pentru un element de pe pozitia i prima pozitie din dreapta mai mare ca a[ i ] si prima pozitie din stanga mai mare ca a[ i ]. Sa zicem ca vrem sa determinam prima pozitie din stanga mai mare ca a[ i ] pentru fiecare i. Parcurgem elementele pe rand. O sa le inseram in stiva pe fiecare scotand din stiva toate elementele mai mici ca elementul curent inserat. Este destul de clar ca ultimul element ramas nescos din stiva o sa fie primul element din stanga pozitiei curente mai mare ca elementul curent. Titlul: Răspuns: 803 Secvmax Scris de: Sima Cotizo din Februarie 20, 2009, 18:25:59 Acum este mult mai clar! Multumesc!
Titlul: Răspuns: 803 Secvmax Scris de: Paduraru Ciprian - Ionut din Martie 02, 2009, 17:06:29 Salut !
Am implementat si eu problema asta si primesc 70, iau la ultimele 2 teste TLE. Sa fie de la quicksort implementat in stdlib , sa prinda un test in cel mai defavorabil caz ? :D Altfel nu-mi explic ca e acceasi complexitate ca in solutia oficiala. Titlul: Răspuns: 803 Secvmax Scris de: Dragos Oprica din Martie 02, 2009, 18:23:39 Salut ! Am implementat si eu problema asta si primesc 70, iau la ultimele 2 teste TLE. Sa fie de la quicksort implementat in stdlib , sa prinda un test in cel mai defavorabil caz ? :D Altfel nu-mi explic ca e acceasi complexitate ca in solutia oficiala. daca esti sigur ca este de la quick sort poti incerca sa sortezi cu sort din STL: Cod: #include <algorithm> unde sort sorteaza vectorul a cu elementele de pe pozitiile 0..n-1 Titlul: Răspuns: 803 Secvmax Scris de: Paduraru Ciprian - Ionut din Martie 03, 2009, 11:08:26 brici merge STL-ul asta =D>
Titlul: Răspuns: 803 Secvmax Scris de: Danci Emanuel Sebastian din Martie 19, 2009, 08:50:01 pentru sirul 1 4 3 2 5 si val cautata 5 ce ar trebui sa dea?
Titlul: Răspuns: 803 Secvmax Scris de: Andrei Misarca din Martie 19, 2009, 17:33:22 5
Titlul: Răspuns: 803 Secvmax Scris de: Danci Emanuel Sebastian din Martie 19, 2009, 20:54:08 Atata imi da si mie si totusi iau 0. Pe toate testele pe care am incercat imi da bine... Poate cineva sa ma ajute? Macar un test sa vad de ce nu-mi da bine...
Titlul: Răspuns: 803 Secvmax Scris de: Ionescu Robert Marius din Mai 01, 2009, 18:15:56 Dati-mi si mie un test mai mare , ca nu inteleg de ce iau 0 puncte :-k
Titlul: Răspuns: 803 Secvmax Scris de: Gabriel Bitis din Mai 01, 2009, 20:16:29 Genereaza tu un test mai mare, si eu iti zic raspunsul.
Titlul: Răspuns: 803 Secvmax Scris de: Ionescu Robert Marius din Mai 03, 2009, 12:37:11 Cod: 81 10 Cod: 1 L.E: solved :D (multumesc celor care imi dau minus :D) ;) tot asa ;) Editat de moderator: Foloseste tagul [ code ] cand postezi teste. Titlul: Răspuns: 803 Secvmax Scris de: Ababab din Mai 06, 2012, 22:15:25 Îmi dă și mie cineva un indiciu (cât de mic) cum se face problema asta cu păduri de mulțimi disjuncte (sau ceva asemănător)?
Mulțumesc. Titlul: Răspuns: 803 Secvmax Scris de: Paul-Dan Baltescu din Mai 07, 2012, 04:42:48 http://infoarena.ro/algoritmiada-2009/runda-3/solutii#secvmax
Titlul: Răspuns: 803 Secvmax Scris de: Ababab din Mai 07, 2012, 10:57:43 Mulțumesc pentru link, deși îl citisem înainte.
Problema mea era că nu făceam union-by-size, a mers brici după. :) Titlul: Răspuns: 803 Secvmax Scris de: Mihai Visuian din Septembrie 14, 2012, 20:52:25 Cat trebuie sa dea pentru testul de mai sus?
Titlul: Răspuns: 803 Secvmax Scris de: Mihai Calancea din Septembrie 14, 2012, 20:54:48 Cam cat de sus?
Titlul: Răspuns: 803 Secvmax Scris de: Valeriu Motroi din Iunie 27, 2017, 21:10:55 Poate ar trebui marita un pic limita de timp ...
|