014 Secventa

[•fireatmyself]

in 99% din cazuri SIGSECV (Killed by signal 11) semnifica faptul ca ai accesat o zona de memorie pe care nu ai alocat-o inainte. spre exemplu apare daca scri urmatorul cod:

Cod:

int v[100];
printf("%d", v[107]);

aici poti citi (daca n-ai citit deja ) mai multe despre erorile intoarse de evaluator.
incearca sa-ti genereze teste mari, care sa tinda spre marginea valorica superioara a datelor de intrare si vezi unde crapa

[•k_ounu_eddy]

Stiu ce am gresit.Credeam ca trebuie sa afisez valoarea cea mai mare.
Cu toate asta tot primesc SIGSEGV(am refacut problema de la 0).Nu cred ca imi trece de limita unui vector,daca era asa trebuia sa imi mearga macar un test,ca doar nu toate au N-ul maxim

[•fireatmyself]

nu pot sa te ajut mai mult daca nu vad codul sursa... daca vrei poti sa mi-l trimiti prin mail la [email protected].

[•k_ounu_eddy]

Am trimis

[•RaduP]

Iacob Eduard : In loc sa mai postezi in disperare doar tampenii pe forum, mai bine ai sta si te-ai gandi inainte sa scrii ceva.

[•k_ounu_eddy]

Si ma rog ce tampenii am scris pe forum?Daca solutia mea este incorecta ,asta nu inseamna ca am scris tampenii,pot sa trimit orice vreau eu ca solutie(aproape),nu am pus pe nimeni sa se uite pe sursa mea.Daca s-a oferit Bogdan A. Stoica(caruia ii multumesc),asta a facut-o din proprie initiativa,nu ca l-am pus eu.Oricum lasa,nu am chef de cearta...

[•Florian]

La problema asta iau Kill by signal pe toate sursele pe care le-am trimis. Si nu stiu din ce cauza... ](*,)ar putea cineva sa mi dea vreun sfat???

[•astronomy]

Killed by signal: Cea mai frecventa eroare cand ai un bug in program. Cand un program incalca anumite conventii in UNIX acel program primeste un "semnal" care de cele mai multe ori il opreste. Cateva semnale comune:
    * 11(SIGSEGV): Segmentation fault. Asta in 99% din cazuri inseamna ca ai probleme cu accesul la memorie. Ai iesit din limitele unui vector, ai facut stack overflow, etc.
    * 8(SIGFPE): Floating point error. Cauza cel mai frecvent de impartiri la 0.

[•Bluedrop_demon]

O mica intrebare : E posibil sa existe un rezultat cu secventa mai lunga de k ? Mie mi se pare ca e imposibil, adica "minimul" dintr-o secventa mai lunga decat k se gaseste si intr-o secventa de k cu siguranta. Iar cum se cere prima si cea mai scurta, trebuie sa aiba exact k, nu ?

[•pauldb]

Evident .

[•anouk]

am citit un post mai vechi despre o implementare cu deque... oare ar putea cineva sa explice putin ideea? din fragmentul acela de cod nu prea am inteles cum functioneaza..

[•devilkind]

la fiecare pas bagi un element pe la capatu cozii si le scoti pe cele dinaintea lui de care nu ai nevoie. Apoi vezi de la inceputu cozii elementele care nu mai fac parte din secventa care iti trebuie tie si le scoti. Cam asta ar fi in mare.

[•anouk]

merci 

[•Florian]

multumesc Airinei Adrian. Insa mi-am dat seama k luam KBS 11 din cauza k nu am scris corect fiserele de intrare si iesire...am corectat sursa si iau doar 80 de puncte...cu TLE pe ultimile doua...stie cineva de 100??

[•pauldb]

Daca lucrezi in C++ incearca sa folosesti scanf in loc de cin. Poti si sa parsezi citirea.

[•Bluedrop_demon]

De aproape o saptamana caut pe net si citesc toate materialele despre stiva/coada deque. Si totusi ceva imi scapa pentru ca nu reusesc deloc sa pricep cum functioneaza. Am ajuns la concluzia ca trebuie construita o stiva la fiecare pas, parcurgand intervalul i-k+1, i cu o variabila j, dar asta ar iesi din timp. Am citit si solutia de la "trans" si mi se pare la fel de ambigua. Ai o coada in care pui si scoti elemente la fiecare pas, si poate fi chiar vida la un moment dat... Si verifici daca primul element e la distanta < k  de i, si daca nu e il elimini si verifici pentru urmatorul... si daca avem o coada goala ?

Ma poate ajuta cineva cu indicatii mai explicite va rog. Daca e prea evident pentru oricine si duc eu lipsa de anumite calitati de intelegere, poate sa-mi trimita mesaj numai mie pls.

[•astronomy]

Stiva nu o construiesti la fiecare pas, ea deja e construita cu elementele cu indici mai mici decat i (daca acum esti la pasul i). Mai trebuie sa introduci elementul de la pasul i si sa le scoti pe alea care nu sunt bune. Mai vezi si aici ceva detalii http://infoarena.ro/forum/index.php?topic=1190.0

[•Bluedrop_demon]

Ok... cred ca am priceput ce si cum  ma incurcam pentru ca mi se parea ciudat folosirea unui singur vector dar intr-adevar mai trebuia si unul de pozitie.
Am scris urmatorul algoritm (daca nu e bine ca l-am postat va rog sa-l stergeti) care merge pe exemplu dar imi ia 0 puncte:

Cod:

             ul = 1; pr = 1;
             q = 1;
             nr[1][1] = sir[1];
             nr[1][0] = 1;
             max = -MAXIM;
             for( i=2; i<=n; i++ )
                  {
                       while( ( ul > pr-1 ) && ( sir[i] < nr[ul][1] ) ) ul--;
                       ul++; 
                       nr[ul][1] = sir[i]; 
                       nr[ul][0] = i; 
                       while( ( i - nr[pr][0]+1 > k ) && ( pr < ul+1 ) ) pr++;
                       if( ( pr < ul+1 ) && ( nr[pr][1] > max ) )
                           {
                                q = nr[pr][0];
                                max = nr[pr][1];
                           }    
                  }

unde in "sir" am numerele, "nr[ i ][ 1 ]" coada deque si "nr[ i ][ 0 ]" pozitia in sirul initial a elementului i din coada. Imi spuneti si mie ce e in nereg  ?

[•devilkind]

incearca sa faci un brut force, da-ti teste si vezi unde crapa programul tau. App ai putea observa ca stiva la aceasta problema nu prea are cum sa devina vida

[•Bluedrop_demon]

Am intrat de tot in ceata. Pai algoritmul meu, in momentul in care primul element nu e cel mai mic (adica si in exemplu) deja coada devine vida. Deci pana la urma nu am priceput eu cum se face...  am studiat degeaba o sapt... ufff

[LE]
Am implementat stiva "deque" complexitate liniara. M-am prins cum functioneaza numai ca imi iese din timp pe ultimul test. De fapt cateodata imi iese pe ultimele doua teste, alteori doar pe ultimul (daca trimit aceeasi sursa de mai multe ori)... nu este totusi prea stransa limita de timp ?

[•devilkind]

vad ca lucrezi in c++. Incearca sa citesti numerele ca string si apoi sa prelucrezi acel string ptr a ajunge la vectorul de numere. (parsezi citirea)

[•gabitzish1]

imi explica si mie cineva.. ca unui nestiutor.. cum se face un brut force ?

[•amadaeus]

imi explica si mie cineva.. ca unui nestiutor.. cum se face un brut force ?

Pur si simplu verifici toate secventele posibile

[•gabitzish1]

eu vreau sa aflu in ce consta un program brut force ... sa pot aplica si la alte programe.. de multe ori vreau sa verific programele pe teste mai complicate.. si cand ceream pe forum, mi se spunea sa'mi fac un program brut force..... si .. nu stiam cum

[•Bluedrop_demon]

Programele brut force sunt rezolvarile "mai clare" ale problemelor. Acele rezolvari mai usor de descoperit dar cu complexitati mult mai mari O(N^3) sau un BackTracking. Bineinteles ca exista si probleme unde aceste rezolvari se incadreaza in timp, dar acolo unde nu se incadreaza, le folosesti doar ca sa-ti faci teste.

Dai un fisier de intrare ( cu random sau cum vrei, in functie de problema ) si apoi lasi programul "brute-force" (rezolvarea cu complexitate mare) sa ruleze pe testul respectiv, chiar daca dureaza foarte mult. Dupa aceea in fisierul de iesire ai o solutie corecta. (Presupunand ca ai implementat si programul brute-force corect)

Astfel poti incerca alte rezolvari cu complexitate mai mica sa vezi cam cum trebuie sa faci sa iti dea aceeasi solutie ca si programul brute-force.