Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 803 Secvmax  (Citit de 5168 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
wefgef
Nu mai tace
*****

Karma: 1049
Deconectat Deconectat

Mesaje: 3.008


razboinicu' luminii


Vezi Profilul
« : Februarie 15, 2009, 13:34:25 »

Aici puteti discuta despre problema Secvmax.
Memorat

omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
raduzer
Client obisnuit
**

Karma: 62
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #1 : 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.
Memorat
gcosmin
Nu mai tace
*****

Karma: 205
Deconectat Deconectat

Mesaje: 307



Vezi Profilul
« Răspunde #2 : 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.
« Ultima modificare: Februarie 15, 2009, 22:33:50 de către Gheorghe Cosmin » Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #3 : 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.
Memorat
gcosmin
Nu mai tace
*****

Karma: 205
Deconectat Deconectat

Mesaje: 307



Vezi Profilul
« Răspunde #4 : Februarie 19, 2009, 23:38:23 »

Am pus niste explicatii in plus la solutie. Sper sa se inteleaga acum Smile. 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.
Memorat
sima_cotizo
Nu mai tace
*****

Karma: 219
Deconectat Deconectat

Mesaje: 596



Vezi Profilul
« Răspunde #5 : Februarie 20, 2009, 18:25:59 »

Acum este mult mai clar! Multumesc!
Memorat
cip
Strain


Karma: -4
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #6 : 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 ? Very Happy  Altfel nu-mi explic ca e acceasi complexitate ca in solutia oficiala.
Memorat

"concureaza cu tine insuti"
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #7 : 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 ? Very Happy  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
Memorat
cip
Strain


Karma: -4
Deconectat Deconectat

Mesaje: 13



Vezi Profilul
« Răspunde #8 : Martie 03, 2009, 11:08:26 »

brici merge STL-ul asta  Applause
Memorat

"concureaza cu tine insuti"
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #9 : Martie 19, 2009, 08:50:01 »

pentru sirul 1 4 3 2 5 si val cautata 5 ce ar trebui sa dea?
Memorat
Mishu91
Nu mai tace
*****

Karma: 169
Deconectat Deconectat

Mesaje: 751



Vezi Profilul
« Răspunde #10 : Martie 19, 2009, 17:33:22 »

5
Memorat
zalman
Strain
*

Karma: -11
Deconectat Deconectat

Mesaje: 31



Vezi Profilul
« Răspunde #11 : 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...
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #12 : Mai 01, 2009, 18:15:56 »

Dati-mi si mie un test mai mare , ca nu inteleg de ce iau 0 puncte  Think
Memorat
gabitzish1
Moderatori infoarena
Nu mai tace
*****

Karma: 321
Deconectat Deconectat

Mesaje: 926



Vezi Profilul
« Răspunde #13 : Mai 01, 2009, 20:16:29 »

Genereaza tu un test mai mare, si eu iti zic raspunsul.
Memorat
Robytzza
De-al casei
***

Karma: -49
Deconectat Deconectat

Mesaje: 129



Vezi Profilul
« Răspunde #14 : 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 Very Happy
(multumesc celor care imi dau minus Very Happy) Wink tot asa Wink

Editat de moderator: Foloseste tagul [ code ] cand postezi teste.
« Ultima modificare: Mai 03, 2009, 15:44:24 de către Paul-Dan Baltescu » Memorat
psycho21r
Client obisnuit
**

Karma: -15
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #15 : 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.
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #16 : Mai 07, 2012, 04:42:48 »

http://infoarena.ro/algoritmiada-2009/runda-3/solutii#secvmax
« Ultima modificare: Mai 07, 2012, 09:09:40 de către Bogdan-Cristian Tataroiu » Memorat

Am zis Mr. Green
psycho21r
Client obisnuit
**

Karma: -15
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #17 : 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ă. Smile
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #18 : Septembrie 14, 2012, 20:52:25 »

Cat trebuie sa dea pentru testul de mai sus?
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #19 : Septembrie 14, 2012, 20:54:48 »

Cam cat de sus?
Memorat
Djok
Client obisnuit
**

Karma: 10
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #20 : Iunie 27, 2017, 21:10:55 »

Poate ar trebui marita un pic limita de timp ...
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines