803 Secvmax

[•wefgef]

Aici puteti discuta despre problema Secvmax.

[•raduzer]

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.

[•gcosmin]

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.

[•sima_cotizo]

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.

[•gcosmin]

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.

[•sima_cotizo]

Acum este mult mai clar! Multumesc!

[•cip]

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 ?   Altfel nu-mi explic ca e acceasi complexitate ca in solutia oficiala.

[•DraStiK]

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 ?   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

[•cip]

brici merge STL-ul asta 

[•zalman]

pentru sirul 1 4 3 2 5 si val cautata 5 ce ar trebui sa dea?

[•Mishu91]

5

[•zalman]

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...

[•Robytzza]

Dati-mi si mie un test mai mare , ca nu inteleg de ce iau 0 puncte 

[•gabitzish1]

Genereaza tu un test mai mare, si eu iti zic raspunsul.

[•Robytzza]

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
(multumesc celor care imi dau minus ) tot asa

Editat de moderator: Foloseste tagul [ code ] cand postezi teste.

[•psycho21r]

Î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.

[•pauldb]

http://infoarena.ro/algoritmiada-2009/runda-3/solutii#secvmax

[•psycho21r]

Mulțumesc pentru link, deși îl citisem înainte.

Problema mea era că nu făceam union-by-size, a mers brici după.

[•VisuianMihai]

Cat trebuie sa dea pentru testul de mai sus?

[•klamathix]

Cam cat de sus?

[•Djok]

Poate ar trebui marita un pic limita de timp ...