[EDIT: Ooops, las totuși mesajul aici dacă mai are cineva probleme pe viitor.]

Înseamnă că se pasează argumentul prin referință. E util dacă ai un obiect mare și nu vrei să îl copiezi pe tot când îl dai ca argument unei funcții. Mai e util și când vrei să schimbi valoarea unei variabile din interiorul unei funcții, fără să returnezi ceva (unii mai numesc asta returnare prin parametru).

EDIT: Ooops, las totuși mesajul aici dacă mai are cineva probleme pe viitor.

Iau corect doar pe primele 7 teste (fiecare a cate 7 puncte), si cu toate astea iau scor final 50. 

Scorul e normalizat la 100.

O să-mi asum că stai pe Windows, scuze dacă e altfel.

http://www.codeblocks.org/downloads/26

În link-ul de mai sus ai (în momentul în care am scris eu asta) și codeblocks-13.12mingw-setup.exe. Ăsta e un pachet care conține și Codeblocks și portul MinGW al GNU Compiler Collection, mai exact, tot ce îți trebuie ca să te apuci să rezolvi probleme pe infoarena.

Un mic sfat de pe front, nu îți alege facultatea după ce limbaj se studiază mai mult sau mai puțin.

Un alt sfat ar fi să nu pui deloc atâta accent pe un limbaj de programare încât să alegi prea multe în funcție de asta. Poate doar un job, deși e de discutat și cazul ăsta.

O să vrei să înveți mult mai multe limbaje, nu doar C#. Ca și programator vei fi pus în situații în care ți se va da o problemă, un proiect, o idee, etc, iar alegerea limbajului va trebui să o faci tu. În cazul în care, din anumite motive, vrei totuși să fii foarte bun în C#, poți realiza asta doar singur și din experiență, facultatea nu îți va oferi prea multe oricum, oricare ar fi ea.

Poți lua chiar acum o carte, un curs pe internet, sau mai bine, o idee de un proiect destul de mic la care să lucrezi în C#. Spor!

WinBGIm e tehnologie destul de veche, nici nu prea merge bine pe arhitectură x64, plus că nu prea există resurse multe pe internet din care poÈ›i învăța.  ÃŽÈ›i recomand să încerci să faci ceva în SDL, unde È›i-aÈ™ putea răspunde È™i eu la câteva întrebări, dacă ai nevoie.

Poți încerca articolele lui Lazy Foo ca și punct de plecare. Pentru SDL 2.0 nu știu exact cum sunt, dar pentru 1.0 erau bune, simple și la obiect. Alte resurse mai există, trebuie doar să faci o căutare.

Un alt sfat ar fi să încerci Code::Blocks, și probabil să compilezi cu MinGW. Pe astea două le poți descărca la pachet de pe site-ul Code::Blocks.

Știu că nu am răspuns la întrebare, dar realitatea este că prin unele locuri pe la noi se predau la școală tehnologii foarte învechite, și mai sunt oameni pe care îi deranjează asta, chiar dacă nu îi afectează direct.

SIGSEGV este un semnal pe care, de obicei, sistemele tip unix la trimit proceselor care comit segmentation facult, sau mai exact access violation. Acest lucru întâmplă atunci când încerci să accesezi o zonă de memorie care nu îți este destinată. De exemplu, dacă ai declara un vector de 10 elemente int a[10] și după ai vrea să folosești a[15], ar fi foarte probabil ca programul tău să primească SIGSEGV.

Recomand să citești acest articol din documentația evaluatorului de pe infoarena.

În programa pe care am găsit-o eu văd că scrie cam ce ar trebui să știe un elev, nu ce ar trebui să nu știe. Plus că nu scrie nimic de biblioteci. Cel mai apropiat lucru este că programa conține „subprograme predefinite - subprograme, mecanisme de transfer prin intermediul parametrilor, proceduri şi funcţii predefinite” și că „identificarea şi utilizarea subprogramelor predefinite elementare” intră la competențe de evaluat. Nici în programele școlare nu am găsit prea multe (clasa a IX-a, clasa a X-a, clasa a XI-a, clasa a XII-a). Nu se precizează nimic nici pe subiecte și nici pe bareme.

Am omis eu ceva?

Dacă se interzice clar folosirea anumitor biblioteci, nu ar trebui la fel de clar specificat acest lucru pe foaia cu subiectul de examen?

Cât despre facultăți, am impresia că nu există o regulă generală.

La cât de bine se desfășoară educația în România, cred că nici nu există un răspuns clar dacă ai sau nu voie.

Cert e că în liceu nu se studiază. Se poate întâmpla să nimerești la un corector care nu a mai auzit de STL și de bibliotecile alea și să îți considere greșit ce ai scris. Indicat ar fi să nu folosești. Da, poți face contestație după, dar îți pot zice că de fapt chiar nu ai voie sau mai știu eu ce. Mai bine să eviți toate astea.

În altă ordine de idei, nici nu ai nevoie mare de STL la problemele de bac. Cu toate că uneori ți-ar ușura munca, se pot face și fără. Pentru bac eu zic că îți ajunge să știi, ca și biblioteci, cstring, cmath, și cctype, și ceva cu care să faci input/output.

Salut!

O primă propunere ar să pui codul aici ca să vedem dacă e ceva în neregulă cu el.

Aș zice că programul tău ia datele de intrare (cele două numere pe care vrei să le aduni) de la tastatură (de exemplu cu cin >>). În caz că e așa, timpul pe care îl vezi acolo include și secundele cât programul tău a aștept pentru datele de intrare. Recomandarea aici ar fi să citești din fișier sau din altă parte și vezi dacă problema se remediază.

O altă problemă posibilă, deși nu cred că ăsta e cazul, ar putea fi că, dintr-un motiv anume, Code::Blocks-ul îți cronometrează și timpul de preprocesare, compilare, asamblare, etc, care este adăugat la cel de execuție. Din câte îmi amintesc, Code::Blocks nu făcea asta, dar nu am mai lucrat de ceva vreme.

[termen]

Da, recunosc și eu că soluțiile oficiale de la problemele de la olimpiade și implementarea lor lasă de dorit uneori.

Luând în calcul că problema s-a mai dat la olimpiadă, și o soluție este deja existentă pe internet, o să-mi iau libertatea să dau și eu o descriere a aceleiași soluție. Cu toate astea, ca să nu se supere lumea pe mine, o să dau și ceva lucruri mai generale, poate învățăm cu toții din asta.

Trecând peste partea cu determinarea numărului de cuvinte din datele de intrare, avem în față o problemă clasică de programare dinamică, dar puțin deghizată, ce-i drept.

Acum probabil întrebarea este ce este programarea dinamică și de unde vine ea?

Un lucru este sigur, nu are legătură cu alocarea dinamică sau alte chestii legate de limbajul de programare. Zic asta pentru că am văzut că mai există confuzii pe alocuri când se aude prima dată de acest termen. Termenul de programare dinamică a fost folosit prima dată de către Richard Bellman în 1953. Pe atunci nu se prea scria cod, iar termenul de programare era mai degrabă folosit cu sensul de plănuire. Programarea dinamică este doar o metodă de rezolvare a unor probleme.

Ideea e cam așa – dându-ni-se o problemă, am putea da soluția corectă dacă am ști de dinainte soluția pentru una sau mai multe probleme mai mici?

De exemplu, problema ar putea fi: să se determine f₂₀ , al 20-lea termen al È™irului lui Fibonacci. Am putea da pe loc soluÈ›ia problemei dacă am È™ti al 18-lea È™i al 19-lea termen, f₂₀ = f₁₈ + f₁₉ . Pentru că suntem programatori, să facem deja È™i un program pentru determinarea unui asemenea termen Evident, nu o să facem un program care doar ne afiÈ™ează al 20-lea termen, sau doar al x-lea termen, ci o să facem un program care ne dă al n-lea termen, pentru un n luat cumva din niÈ™te date de intrare. Știm că, în general, pentru determinarea unui termen al È™irului lui Fibonacci ne este de ajuns să cunoaÈ™tem cei doi termeni precedenÈ›i ai È™irului. Dacă îi cunoaÈ™tem, putem folosi imediat formula f_n = f_n-2 + f_n-1 È™i să obÈ›inem rezultatul. Dacă nu îi cunoaÈ™tem, atunci vrem să îi calculăm. Observăm că am obÈ›inut acum alte două probleme, dar care sunt mai mici decât cea iniÈ›ială. Putem folosi iar formula de recurență a È™irului lui Fibonacci ca să obÈ›inem câte alte două probleme pentru fiecare din cele două obÈ›inute precedent, mai exact f_n-1 = f_n-3 + f_n-2 È™i f_n-2 = f_n-4 + f_n-3. Putem continua în aceasă manieră până când ajungem la o problemă pe care o putem rezolva trivial, aceea se va numi cazul de bază (pot fi È™i mai multe). ÃŽn situaÈ›ia noastră, cazurile de bază sunt f₁ = f₂ = 1. Am obÈ›inut deci un algoritm recursiv care ne rezolvă problema determinării unui termen de indice n al È™irului lui Fibonacci pentru un n arbitrar. Să vedem È™i codul în C++ pentru un astfel de algoritm.

Cod:

int fibonacci(int n) {

  if (n == 1 || n == 2) {
    return 1;
  }

  return fibonacci(n - 2) + fibonacci(n - 1);
}

Cu toate că folosind acest algoritm recursiv obținem soluția corectă, algoritmul este ineficient. Dezvoltând după formula de recurență, putem observa că recalculăm inutil unii termeni ai șirului.

(arbore de recurență de adâncime 3 pentru formula generală f_n = f_n-2 + f_n-1 a unui număr Fibonacci, figură realizată cu yEd)

ÃŽn arborele de recurență de mai sus se observă că f_n-4 este calculat deja de 4 ori. Dacă am extinde arborele, am observa că f_n-4 este calculat chiar de mai multe ori. Ca exemplu, următorul tabel ne arată de câte ori calculăm fiecare din primii 5 termeni ai È™irului, dacă folosim algoritmul de mai sus pentru a calcula f₂₀.

termen	count
f1	2584
f2	4181
f3	2584
f4	1597
f5	987

Clar nu vrem să calculăm f₂ de 4181 ori, până È™i pe hârtie putem face mult mai bine de atât.

Acest fapt ne conduce la o optimizare naturală, care este și o tehnică foarte folositoare la olimpiade și alte concursuri. Aceasta se numește memoizare (engleză - memoization). Termenul a fost folosit prima dată în 1968 de către Donald Michie, care, ca și Alan Turing, a lucrat la Bletchley Park în timpul celui de-Al Doilea Război Mondial. Memoizarea nu este decât faptul de a memora anumite rezultate pentru a nu le recalcula.

ÃŽn exemplul de față, este uÈ™or să facem acest lucru. Concret, vom menÈ›ine un vector de n elemente în care vom memora dacă am mai calculat sau nu înainte un termen È™i, dacă da, care a fost rezultatul. Pentru a vedea dacă am mai calculat sau nu termenul în cauză, vom iniÈ›ializa vectorul cu -1, folosindu-ne de faptul că un termen al È™irului lui Fibonacci este mereu pozitiv, deci dacă vectorul la indicele termenului pe care vrem să îl calculăm este mai mare decât -1 atunci înseamnă că am mai calculat termenul înainte.  Codul în C++ este mai jos.

Cod:

int mem[100];

int fibonacci(int n) {

  if (mem[n] == -1) {
    if (n == 1 || n == 2) {
      mem[n] = 1;
    } else {
      mem[n] = fibonacci(n - 2) + fibonacci(n - 1);
    }
  }

  return mem[n];
}

Folosind memoizare, tabelul de mai sus devine

termen	count
f1	1
f2	1
f3	1
f4	1
f5	1

È™i, mai mult, continuă cu 1 până la f₂₀.

Acestă tehnică este foarte utilă, dar putem mai bine de atât! Putem chiar să scăpăm de recursivitate și să creăm un algoritm iterativ. Ce am făcut mai sus se numește o abordare top-down. Ce urmează să facem se numește, intuitiv, bottom-up.

În cazul șirului lui Fibonacci ne este ușor să trecem la abordarea dorită. Ne este ușor din două puncte de vedere. Primul este că un termen al șirului lui Fibonacci depinde doar de indicile său, este o funcție de o singură variabilă. Al doilea este că formula de recurență este simplă, nu depinde decât de două rezultate precedente.

Întrebarea mai clară aici este am putea calcula valorile vectorului mem în timp liniar, fără a folosi un algoritm recursiv? (partea cu liniar este specifică probleme pe care o rezolvăm acum)

Primul pas ar fi să punem cazurile de bază, mem[1]=1 și mem[2]=1. Următorul pas ar fi să observăm că putem calcula acum mem[3], care este mem[1]+mem[2]. Continuând tot așa pentru mem[4], mem[5], mem[6], etc, obținem un simplu algoritm iterativ pentru a calcula valorile vectorului.

Cod:

mem[1] = 1;
mem[2] = 2;

for (int i = 3; i < n; ++i) {
  mem[i] = mem[i - 2] + mem[i - 1];
}

Acum putem spune oficial că am folosit programare dinamică. Codul de mai sus mai poate fi optimizat, dar optimizarea nu aduce nimic în plus ideii în discuție.

___________________________________________________________

Să încercăm acum să ne îndreptăm acum spre problema Text, de la care a pornit cam toată discuÈ›ia. Problema ne cere mai exact, cum am zis în postările anterioare, secvenÈ›a maximală de cuvinte (nu neapărat consecutive în datele de intrare) care are proprietatea că oricare două cuvinte consecutive din secvență îndeplinesc proprietatea cerută. O pereche de cuvinte îndeplineÈ™te proprietatea dacă È™i numai dacă ultima literă a primului cuvânt este aceeaÈ™i cu prima literă a celui de-al doilea.  Să ne luăm un exemplu mai uÈ™or:

ana are caini andrei are iepuri

Putem reprezenta grafic exemplul cu diagrama de mai jos.


(reprezentarea grafică a exemplului de mai sus, figură realizată cu yEd)

Am pus o săgeată de la un cuvânt la altul dacă ce de-al doilea vine după primul în datele de intrare și ultima literă a primului este prima literă de celui de-al doilea.

Acum problema este mai ușor de văzut, ni se cere să găsim un drum de lungime maximă. Prin drum înțelegem o secvență de cuvinte legate prin săgeți ca în diagrama de mai sus. Evident, săgețile trebuie să fie orientate înspre dreapta, nu puteam schimba ordinea cuvintelor. Pentru asta, vom rezolva probleme similare cu cele în care găseam un termen al șirului lui Fibonacci, dar de data aceasta vom folosi o altă formulă de recurență. Mai exact, problemele pe care vrem să le rezolvăm sunt de tipul care este lungimea maximă a unei secvențe care se termină la al n-lea cuvânt din datele de intrare și corespunde cu cerința problemei? Nu prea sună la fel, dar în realitate este. O să notăm răspunsul la întrebări de genul acesteia cu g_n.

Spre exemplu, cum am putea găsi g₆? Ei bine, lungimea secvenÈ›ei care se terină la cuvântul iepuri este cel puÈ›in 1 pentru că, evident, secvenÈ›a include cel puÈ›in cuvântul iepuri. Desigur, răspunsul nu este chiar 1, dar deja începem să construim o formulă, g₆ = 1 + (ceva) . Observăm acum uÈ™or pe diagramă că singura modalitate de a ajunge la cuvântul iepuri, în caz că nu am plecasem chiar de acolo, este ori prin cuvântul andrei (indice 4), ori prin cuvântul câini (indice 3). Dar nu le putem adăuga pe ambele. Trebuie să alegem una dintre cele două modalități. Èšinând cont că vrem să aflăm lungimea maximă, ar trebui să o adăugăm pe cea cu valoarea g mai mare. Deci, obÈ›inem formula pentru g₆, g₆ = 1 + max(g₃, g₄) . Este indicat să vedem prin această formulă. Practic ea zice că dintre cele două modalități de a ajunge la cuvântul 6, noi o vrem pe cea mai bună, mai bună în acest caz înseamnă mai lungă.

Putem generaliza acum uÈ™or această formulă recurentă. De la un cuvânt de indice n vrem să alegem cel mai lung drum care ajunge la cuvântul n. Deci, mai concis g_n = 1 + max(g_a1, g_a2, ... , g_am) unde cuvintele de indici a₁, a₂, ... , a_n au ca ultimă literă prima literă a cuvântului de indice n.

Acum că È™tim formula, povestea este aceeaÈ™i ca la È™irul lui Fibonacci, putem rezolva problema recursiv top-down, unde putem optimiza folosind memoizare, sau o putem rezolva iterativ bottom-up. Ar fi câteva lucruri de menÈ›ionat. Primul este că răspunsul nu va mai găsit chiar în acelaÈ™i loc ca la Fibonacci, ci vor mai fi de făcut câteva mici calcule. Al doilea este că nu suntem mulÈ›umiÈ›i doar cu găsirea lungimii secvenÈ›ei care trebuie eliminată, ci vrem È™i secvenÈ›a în sine, lucru care se face uÈ™or dacă È›inem minte cumva la fiecare utilizare a formulei g_n = 1 + max(g_a1, g_a2, ... , g_am) ce indice a_k a ales funcÈ›ia max. ÃŽn exemplul de mai sus, pentru iepuri am fi È›inut minte andrei, pentru că la andrei aveam g₄ = 2 iar la câini g₃ = 1, deci era de preferat să fi venit de la cuvântul andrei pentru că drumul era mai lung. Mai exact, È›inem minte de unde am venit. Acest lucru (găsirea subsecvenÈ›ei în sine) nu È›ine direct de programare dinamică, aÈ™a că nu o să îl descriu în detaliu.

Astea fiind zise, avem acum o direcție destul de bună ca să începem să implementăm problema. Din diferite motive, am ales să nu pun aici codul, dar problema se rezolvă, cum am zis mai sus, aproximativ la fel ca cea a șirului lui Fibonacci.

___________________________________________________________

Mai jos sunt câteva chestii puțin mai avansate și care deviază de la subiect.

Este interesant de văzut, pentru cei care sunt la început și deja au învățat despre grafuri, că sub orice problemă de dinamică (i.e. care poate fi rezolvată folosind metoda programării dinamice) stă de fapt un graf aciclic orientat, sau DAG (directed acyclic graph). Chiar dacă problema pare că nu are absolut nicio legătură cu grafurile, ea se poate modela ca o problemă pe un DAG în mod natural. Nodurile DAG-ului sunt subproblemele pe care vrem să le rezolvăm, iar muchiile sunt dependențele între probleme. Dacă alegem această reprezentare, este evident de ce vrem ca graful să fie aciclic – nu vrem dependențe circulare. În problema de mai sus se vede clar acest lucru. Diagrama aceea era de fapt un DAG, iar în formulă foloseam acel max(g_a1, g_a2, ... , g_am) pentru indicii de forma a_k dacă aveam o muchie care pleca de la cuvântul (nodul) de indice a_k și ajungea în nodul pentru care făceam calculul. Găsirea celui mai lung subșir crescător, este exact aceeași problemă ca cea de mai sus, deci acesta este încă un exemplu. Alt exemplu – găsirea celui mai lung subșir comun, graful arată frumos dacă îl aranjăm ca o pânză, adică nodurile puse ca într-un tablou dibimensional, soluția ar fi atunci pe o plimbare dintr-un colț al grafului în colțul opus, fără să schimbăm sensul, soluția în sine ar fi ce obținem dacă selectăm din acea plimbare doar acele mișcări pe diagonală. Aceste grafuri ne oferă, printre altele, o posibilitate de a vizualiza mai clar problemele, scăpând de cea a tablourilor 1-, 2-, 3- sau mai știu cu cât-dimensionale unde mai toate problemele arată la fel – un tablou și-o formulă.

[ion]

Cuvintele nu trebuie neapărat să fie adiacente.

Soluția din exemplu arată cam așa:
pentru ca nu are timp ion spune ca nu urmareste nici emisiuni interesante si evident nici altfel de emisiuni.

Unde cuvintele îngroșate au fost păstrate, iar celelalte eliminate.

Răspunsul este da, ni se cere secvența maximală de cuvinte (nu neapărat consecutive în datele de intrare) care are proprietatea că oricare două cuvinte consecutive din secvență îndeplinesc proprietatea cerută.

Dacă nu te descurci, problema este de la OJI 2010. Găsești soluția în arhiva OJI.

Poți găsi problema și pe infoarena.

Ideea de la Shell sort este că am putea sorta ceva mai rapid dacă am sorta mai întâi elementele mai depărtate.

De exemplu, ca să sortăm toate elementele de distanță 4, trebuie să sortăm separat cele 4 liste formate din

• primul element, al 5-lea, al 9-lea, È™.a.m.d
• al 2-lea element, al 6-lea, al 10-lea, È™.a.m.d
• al 3-lea element, al 7-lea, al 11-lea, È™.a.m.d
• al 4-lea element, al 8-lea, al 12-lea, È™.a.m.d.

Acum lista noastră cea mare (care conține exact cele 4 subliste de mai sus) are proprietatea că de oriunde plecăm, să zicem că de la al i-lea element, elementele de forma i+4k, unde k este număr natural, sunt mai mari sau egale cu elementul inițial, iar cele de forma i-4k, unde k este număr natural, sunt mai mici sau egale cu elementul inițial.

În general, ca să sortăm toate elementele de distanță k, vom împărți lista în următoarele subliste:

• 1, 1+k, 1+2k, 1+3k, 1+4k, È™.a.m.d.
• 2, 2+k, 2+2k, 2+3k, 2+4k, È™.a.m.d.
• ...
• k-1, (k-1)+k, (k-1)+2k, (k-1)+3k, (k-1)+4k, È™.a.m.d.
• k, k+k, k+2k, k+3k, k+4k, È™.a.m.d.

Obținând în total k subliste.

Acum Donald Shell în lucrarea lui (1959) n-a zis exact asta, dar metoda din spatele Shell sort este modulară, în sensul că putem folosi ce algoritm vrem pentru sortarea sublistelor și ce dimensiuni pentru distanțe vrem (atâta timp când ultima este 1).

Dacă am înțeles eu bine, întrebarea ta este cum am putea folosi bubble sort în Shell sort. Ideea este următoarea - dacă avem o listă de elemente de lungime n, vom sorta prima dată toate elementele la distanță n/2 între ele (cum am zis mai sus), apoi cele la distanță n/4, n/8, ș.a.m.d. Această alegere este arbitrară, este una populară totuși, este chiar cea folosită de Donald Shell în articolul original. Cu toate astea, puteam face o cu totul altă alegere, puteam sorta toate elementele la distană n-1, apoi n-2, n-3, etc. Bubble sort în viața de zi cu zi trece direct la sortarea elementelor la distanță 1. Oricum, deci am ales lista de distanțe {n/2, n/4, n/8, ... }. Din prima distanță, vom obține n/2 subliste, după metoda descrisă mai sus. Sortăm toate aceste subliste folosind bubble sort după care luăm următoarea distanță, n/4, din care vom obține n/4 subliste - procedăm analog, și procedăm analog pentru toate distanțele rămase.

Cred că ar trebui să specific că toate sortările se întâmplă pe loc, adică atunci când spunem că sortăm o sublistă sortăm sublista chiar în lista cea mare.

Pentru un exemplu de implementare, poți consulta sursa asta.

Cat de cat, m-ai luminat putin. Dar mai am o singura intrebare, spre exemplu, 5 poate fi descendent al lui 7, si 7 ascendent al lui 5? (2 7 6 5)

Evident. De fapt, nici nu se poate altfel - dacă 5 este descendent al lui 7, atunci 7 trebuie să fie ascendent al lui 5.

La lista de descendenti, ma refeream, cum pot fi scrisi pe o foaia (vreau sa dau bacul la informarica). La fel cum este lista de adiacenta, ca la grafurile neorientate si orientate.

Hmm, să vedem dacă am înțeles. Am făcut un exemplu nou pentru asta, are aceeași structură cu cel de mai sus, dar am redenumit nodurile ca să fie mai clar.

(imagine creată cu yEd)

Pe exemplul ăsta, listele de descendenți pentru fiecare nod în parte ar arăta cam așa:
A: {B, C, D, E, F, G, H, I}
B: {D, E, G, H}
C: {F, I}
D: {}
E: {G, H}
F: {I}
G: {}
H: {}
I: {}.

Ca să obții lista de descendenți a unui nod, te uiți pe arbore și vezi unde poți ajunge plecând de la nodul respectiv și mergând în jos pe muchii.

Bonus, listele de ascendenți pentru fiecare nod:
A: {}
B: {A}
C: {A}
D: {A, B}
E: {A, B}
F: {A, C}
G: {A, B, E}
H: {A, B, E}
I: {A, C, F}.

Pentru lista de ascendenți este exact invers - te uiți pe arbore și, plecând de la nodul căruia vrei să îi faci lista, vezi unde poți ajunge mergând în sus pe muchii.

[descdendent]

La ce te referi mai exact când zici identifica?

Un arbore este un graf aciclic și conex în care ne alegem un nod pe post rădăcină. Doarece avem un graf aciclic conex, există un unic drum elementar între oricare două noduri. Dacă vrem, putem să și orientăm graful dinspre rădăcină înspre exterior (înspre frunze).

• descdendent - un nod A se numeÈ™te descendent al unui nod B dacă È™i numai dacă A este diferit de B È™i drumul elementar de la rădăcină la A îl conÈ›ine pe B
• descdendent direct - un nod A se numeÈ™te descedendent direct al unui nod B dacă È™i numai dacă îi este descendent È™i adiacent
• ascendent - un nod B se numeÈ™te ascendent al unui nod A dacă È™i numai dacă A este descendent al lui B
• ascendent direct - un nod B se numeÈ™te ascendent direct al unui nod A dacă È™i numai dacă îi este ascdendent È™i adiacent

Intuitiv, noțiunile de desendent și ascendent sunt legate una de alta, un nod A nu-i poate fi descendent unui nod B dacă nodul B nu îi este ascendent lui A. Și mai intuitiv, ascendenții unui nod un aceia pe care îi găsești plimbându-te de la nodul tău în sus, înspre rădăcină, deci nodurile care sunt practic deasupra nodului respectiv. Descendenții, în mod analog, sunt aceia pe care îi găsești dedesubt.


(imagine wikipedia)

Pe exemplul din figura de mai sus o să mă refer la nodul cu valoarea x ca nodul x, deoarece valorile sunt unice înafară de valoarea 2, pe care nu o să o folosesc ca să nu dăm în ambiguitate. Deci, avem că, spre exemplu, 11 este descendent al lui 7 (avem drumul elementar 2 7 6 11). Evident, 7 este ascendent al lui 11. Un descdendent direct al lui 7 ar fi 6 (de ce?). Evident, 7 este ascendent direct al lui 6 (iar, de ce?).

Mă îndoiesc că ce-am zis eu aici a făcut prea multă lumină. Dacă nu stăpânești bine noțiunile, recomandarea mea este să îți desenezi chiar tu câțiva arbori și să îți faci câteva exemple pe ei.

Pentru lista de descdenenți, dacă vrei un exemplu în C/C++, depinde cum memorezi arborele. Dacă ai putea da ceva mai multe detalii ar fi super.

Biblioteca vector are ceva mai multe aplicații decât folosirea în listele de adiacență. Încearcă să te documentezi mai mult despre ea, și în general despre ceva numit STL (Standard Template Library), îți va fi de mare ajutor la olimpiade.

De ce mai multe ori cea mai adecvată metodă este lista de adiacență.

Totuși, în unele cazuri, spre exemplu când știi că graful e destul de mic, sau că e dens, poate fi de preferat să folosești matricea.

Ca să facem o analiză, pentru a reprezenta un număr n în baza k ne trebuie cam log_kn cifre. Dacă ne luăm două baze, să zicem a È™i b, numărul n în baza a are log_an, iar în baza b are log_bn = log_an / log_ab. Deci schimbând de la baza a la baza b, numărul cifrelor diferă printr-un factor de log_ab. Deci trecând de la, să zicem, baza 10 la baza 10ⁿ numărul cifrelor diferă printr-un factor de log₁₀10ⁿ = n.

Să presupunem că fiecare întreg are dimensiunea de 4 octeÈ›i fiecare. Un număr de la 0 la 9, pe care-l putem identifica cu o cifră a numărului mare, ocupă maxim jumătate de octet (4 biÈ›i, 2⁴ - 1 = 15). Mai rămân 3 octeÈ›i È™i jumătate pe care îi pierdem.

Lucrând într-o bază mai mare te vei folosi mai mult și de instrucțiunile de operații de bază (mă refer aici la adunare, scădere, înmulțire, împărțire) ale procesorului și mai puțin de instrucțiunile artificiale pentru aceste oprații din programul tău.

Acum dacă ținem cont că baza maximă pe care o putem folosi ar fi cam 9 dacă folosim 4 octeți pe întreg sau 18 dacă folosim 8 octeți, ne putem întreba dacă un factor de maxim 18 merită să facem acest artificiu.

Desigur că merită să lucrezi într-o bază cât de mare ți se permite pentru că odată ce te-ai prins cum să implementezi, o să observi că nu e prea diferit de atunci când folosești baza 10 (schimbi pe acolo niște zero-uri și ai grijă la afișare). Practic depunem foarte puțin efort pentru un avantaj destul de semnificativ uneori.

Ca un exemplu concret la ce am zis mai sus - unele probleme chiar de pe infoarena nu pot fi rezolvate de 100p lucrând cu numere mari în bază 10, dar intră foarte bine în timp cu același algoritm, folosit însă cu o bază ceva mai mare.

Etapa de preprocesare e cea în care se analizează liniile ce încep cu # ca și directive. O directivă este o instrucțiune care specifică cum ar trebui să acționeze compilatorul / assemblerul. O eroare de preprocesare este o eroare pe una din aceste linii.

Spre exemplu,

Cod:

#include <stdio.h>

int main() {
  
  printf("Hello World!\n");
  
  return 0;
}

este un program valid în C. Dacă, în schimb, am face

Cod:

#include <not_a_file.h>

int main() {
  
  printf("Hello World!\n");
  
  return 0;
}

am obține o eroare la faza de preprocesare pe motiv că nu s-a putut găsi fișierul not_a_file.h.

Erorile de preprocesare nu trebuie neapărat să fie neintenționate, spre exemplu

Cod:

#include <stdio.h>

#if (__STDC_VERSION__ != 201112L)
#error C11 or later required.
#endif

int main() {
  
  printf("Hello World!\n");
  
  return 0;
}

spune că noi nu vrem să compilăm decăt cu standardul C11 sau mai nou. Făcând gcc -std=c99 test.c vom obține iarăși o eroare în faza de preprocesare care ne transmite mesajul scris de noi pe linia cu #error. Pe de altă parte, gcc -std=c11 test.c va funcționa fără probleme.

Se pot face destul de multe lucruri interesante cu aceste directive.

Erorile de compilare sunt cele care au loc în timp ce compilatorul încearcă să traducă codul tău în alt limbaj (în cazul nostru, din C în limbaj de asamblare). Cum s-a zis și mai sus, acestea sunt, de obicei, cele „clasice”. Pot apărea însă, mai rar, erori și în compilator (internal compiler error). Următorul fragment este luat de pe Wikipedia:

Cod:

somefile.c:1001: internal compiler error: Segmentation fault
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://bugs.gentoo.org/> for instructions.

Poți lua o carte de C++ (dacă iei, ai grijă ce carte iei) și să înveți progresiv, dar nimic nu se compară cu experiența pe care o capeți lucrând.

Edit: când am zis lucrând nu mă refeream neapărat la un job, ci la lucrând acasă de bunăvoie.

Cod:

// compilat cu g++-4.9 -std=c++11

#include <iostream>

using namespace std;

int main() {

  uint64_t a = 0;
  cout << (a - 1) / 10 << (a - 1) % 10 + 1 << "\n";

  return 0;
  
}

Pe 64 de biÈ›i nu îți încape 2⁶⁴.

[Edit:]

Nu poți face acest lucru direct din citire deoarece nu știi când vine ultimul număr negativ. Tot ce poți face e să salvezi începând de la primul număr negativ și după să scapi de tot ce este după ultimul număr negativ. Ai mai jos un exemplu cum ai putea face acest lucru.

Cod:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int main() {

  ifstream f("date.in");

  int x;

  bool on = false;
  int last = -1;

  vector <int> secv;

  while (f >> x) {
    if (x < 0) {
      on = true;
    }

    if (on) {
      secv.push_back(x);
    } 
  }

  while (secv[secv.size() - 1] > 0) {
    secv.pop_back();
  }

  for (int i = 0; i < (int)secv.size(); ++i) {
    cout << secv[i] << " ";
  }
  cout << "\n";

  return 0;
}

Edit: scuze, acum abia acum am văzut că postul e de acum 7000 de ani.

Ceea ce ai scris tu acolo în C++ este undefined behaviour.

>> și << sunt operatori, iar în C++ nu există conceptul de evaluare de la dreapta la stânga sau de la stânga la dreapta, deci mai clar nu există conceptul de ordinea evaluării. A nu se confunda cu asociativitatea operatorilor de la stânga la dreapta sau de la dreapta la stânga.

f() + g() + h() se evaluează ca (f() + g()) + h(), dar h() s-ar putea să fie funcția evaluată prima, și abia după să se treacă la paranteză.

În altă ordine de idei, când programezi cu side effects, încearcă să nu apelezi două funcții în aceeași expresie, mai ales dacă este importantă ordinea în care ele sunt apelate.

Uite un exemplu. Eu când compilez cu g++-4.9, codul

Cod:

int i = 0;
cout << i << " " << i++ << "\n";

îmi afișează 1 0. Cu toate astea, nu este indicat să te bazezi pe exemplul ăsta, încearcă să găsești altă soluție.

Un alt exemplu interesant.

Cod:

int i = 0;
if (++i || ++i) {

}
cout << i << "\n";

afișează 1, pe când

Cod:

int i = 0;
if (i++ || ++i) {

}
cout << i << "\n";

afișează 2. Motivul este acela că atunci când ai un sau logic între doi operanzi, este suficient ca primul operand să fie evaluat ca adevărat pentru ca expresia să fie evaluată și ea ca fiind adevărată. Prin urmare, dacă primul operand este adevărat, cel de-al doilea nici nu se mai evaluează deoarece se cunoaște valoarea expresiei deja. În caz contrar, dacă primul operand se evaluează ca fals, atunci este necesară și evaluarea celui de-al doilea operand. Aici, cu toate că avem o expresie cu doi operanzi și un operator, ordinea evaluării lor este definită. Mai exact, într-o expresie de forma să zicem a || b există un sequence point după a. Existența unui sequence point denotă faptul că toate side effect-urile evaluărilor precedente trebuie să fie terminate și că nici un side effect al vreunei evaluări ulterioare nu a avut loc.

N-ar trebui să fie sigma inclus în {a, b, c, ...}  în loc de sigma aparÈ›ine {a, b, c, ...}?

Dacă îți place cartea de Mathematics for Computer Science (cartea pe care a postat-o klamathix mai sus), te poți uita și la cursul aferent ei aici. Leighton e un profesor foarte bun, dă explicații intuitive. Marten van Dijk era în vizită la MIT mi se pare, dezavantajul lui este că are un accent cam dubios, dar dacă treci peste asta înveți multe de la el.

Dacă implementezi cu liste de adiecență probabil nu e nevoie, dar dacă implementezi cu matrice o să ai ceva probleme pentru că presupunem că în graful rezidual u -> v e cât mai putem să trecem prin arcul de la u la v și v -> u cât am trecut deja, apoi dacă ar exista în rețea și arcul v -> u simultan, arcele în graful rezidual ar avea un înțeles ambiguu. Poți desigur să menții două matrice de graf rezidual, dar deja dezvoltăm prea mult un subiect care nu e chiar atât de important.

Oricum, enunțul a fost modificat, zic acum să sărbătorim.