infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Andrei Grigorean din Februarie 15, 2009, 13:34:25



Titlul: 806 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: 806 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: 806 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: 806 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: 806 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: 806 Secvmax
Scris de: Sima Cotizo din Februarie 20, 2009, 18:25:59
Acum este mult mai clar! Multumesc!


Titlul: Răspuns: 806 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: 806 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>
using namespace std;
...
int main ()
{
    ...
    sort (a,a+n);
    ....
}

unde sort sorteaza vectorul a cu elementele de pe pozitiile 0..n-1


Titlul: Răspuns: 806 Secvmax
Scris de: Paduraru Ciprian - Ionut din Martie 03, 2009, 11:08:26
brici merge STL-ul asta  =D&gt;


Titlul: Răspuns: 806 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: 806 Secvmax
Scris de: Andrei Misarca din Martie 19, 2009, 17:33:22
5


Titlul: Răspuns: 806 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: 806 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: 806 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: 806 Secvmax
Scris de: Ionescu Robert Marius din Mai 03, 2009, 12:37:11
Cod:
81 10
1 5 25 34 6 46 4 73 72 2 72 4 4 23 5 6 8 5 32 346 4 347 5 867 9 56 73 512 1 45 125 36 4 7 7 587 34 63 25 12 512 5 36 4 57 43 7 467 58 54 7 37 247 534 6272 562 6 67 67 6 56 3 3 5 67 84 2 72 876 1 2 3 4 5 3 5 66 5 4 363 6456
1
53
525
72
73
100
123
125
126
14
Rezultate:
Cod:
1
8
23
11
19
19
19
19
19
7

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: 806 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: 806 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: 806 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: 806 Secvmax
Scris de: Mihai Visuian din Septembrie 14, 2012, 20:52:25
Cat trebuie sa dea pentru testul de mai sus?


Titlul: Răspuns: 806 Secvmax
Scris de: Mihai Calancea din Septembrie 14, 2012, 20:54:48
Cam cat de sus?


Titlul: Răspuns: 806 Secvmax
Scris de: Valeriu Motroi din Iunie 27, 2017, 21:10:55
Poate ar trebui marita un pic limita de timp ...