Timpul alocat întrebărilor s-a scurs. Multă baftă în continuare!

Fara comentarii.

1. Problema cere un subarbore de cost minim care sa contina cele T noduri. Nu conteaza ce alte noduri ai sau nu ai, atata timp cat cele T sunt acolo si costul e minim.
2. DA, poate sa contina si altele

Fara comentarii.

Am adaugat feedback pe testele 1 si 6 si am facut o mica reevaluare Re-verificati-va sursele  Succes!

Fara comentarii.

Pot fi si 0.

Cred ca se intelege destul de clar din exemplu ca B trebuie sa fie "in ordine."

Nu am inteles intrebarea, reformuleaza te rog intr-un mod mai clar.

Greseala mea, eu am vorbit mai mult de SUA pentru ca asta ma intereseaza mai mult. Din punct de vedere financiar, e o diferenta uriasa intre UK si US, in special pentru romani (majoritatea): in UK, orice ar fi, ai de platit cele 9000 de lire + costurile de intretinere, adica ajungi undeva pe la 12-13 mii (lire repet), sper ca nu vorbesc prostii prea mari. E un pret mare, asa e, dar mi se pare ca pentru educatie merita sa faci investitia asta.

In State, educatia e scumpa. Costa ~ 60.000 de dolari pe an. Din fericire, multe facultati (din cele pe care le stiu eu) acorda ajutor financiar, iar majoritatea le dau si internationalilor. Cele de top spun urmatoarea chestie: "we meet 100% financial need", adica dupa ce faci dovada veniturilor parintilor ei iti fac o oferta de financial aid, si se intampla destul de rar sa ceara peste 20-25% din cat castiga parintii tai (de obicei cer mai putin). Banii astia li se duc parintilor pe tine oricum si cat esti in Romania .

[Later Edit]: Bogdan zice ca si in UK e bine cu banii , stie mai bine. Nu lua in seama primul meu paragraf

Parerea mea legata de toata treaba asta cu universitatea in strainatate e ca diferenta uriasa nu e in cunostinte. Cunostintele la urma urmei le poti dobandi si singur, citind mult, uitandu-te la cursuri pe net, lucrand etc. Ce mi se pare mie ca e cel mai tare la universitatile de top e in primul rand mediul in care te afli. Evident ca atunci cand ai 2 profesori care au luat Nobel, unul care a luat medalia Fields, si nustiucati colegi care au fost finalisti la Intel sau au rezultate majore la competitii de top, esti motivat sa tragi tare si sa iesi in fata. Apoi mai e posibilitatea de a incerca aproape orice materie iti doreste sufletul. Vrei sa faci informatica super bine si in acelasi timp sa inveti psihologie? La MIT / Harvard / Yale / etc. poti cu siguranta. Vrei double major info - mate si minor in economie? Again, daca lucrezi suficient de mult, poti. Legat de MIT: poti sa-ti iei pana si degree de pirat, daca faci cateva cursuri specifice . Cred ca la UNIBUC e putin mai dificil.

La urma urmei, daca vrei sa ajungi Software Engineer la Google / Facebook / etc., poti sa faci asta si din tara si din strainatate. pentru ca tine de nivelul de pregatire, nu de brandul care e scris pe tine. Ca dintr-o facultate de top ti se ridica si alte oportunitati (probabil mai multe, e adevarat). Dar motivul principal pentru a merge acolo mi se pare efectiv chestia aia careia elevii americani ii zic "college experience".

Aparent  . Hai, gata cu offtopicul, se discuta chestiuni serioase aici . Nichita, nu te mai aventura in afirmatii de genul ala, s-ar putea ca nu toti sa iti impartaseasca parerile. Si in plus, putin respect pentru batranul C . Chiar daca nu iti place Morgan Freeman de exemplu, nu zici despre el ca e un actor prost, pentru ca toti stiu ca e bun. Il respecti si taci din gura.

Si mie mi se pare ca prunele le sunt net superioare usilor rotative.

La clasele 11-12 e necesara cam "toata materia"... uita-te peste arhiva educationala, vei gasi acolo cam tot ce ai nevoie pentru a lua premiul I la ONI si pentru a intra in lot Spor!

Felicitari lui Adi Budau pentru super-performanta de a ajunge rosu pe TopCoder!!!
Keep up the good work Adi, pana la target nu te opri



 

OMFG! FELICITARI ECHIPEI PENTRU IMBUNATATIRILE FACUTE LA SITE! MERGE INSTANT!

[12 secunde]

Cand se vor baga in arhiva pb ?

Ah, la naiba! Ai devenit nerabdator in cele 12 secunde de cand s-a terminat concursul?

Intrebam si eu ....
App ... la problema minsweeper, o sa se puna ceva solutii oficiale, sunt foarte curios care era ideea de 100 puncte ...

Solutia oficiala, din ce-am vazut eu acuma (pe sursa lui Voroneanu) este ideea ca la problema Turnul Tunelul groazei de pe infoarena.

Da, rezolvarea e pe acelasi principiu.

Eu zic asa sa arate si solutia oficiala  . Sa vedem cum apar sursele in arhiva.

Aparent sursele sunt open => ele vor aparea in arhiva ca ciupercile dupa ploaie.

Ca o concluzie finala a concursului, felicitari tuturor participantilor! Ne bucuram ca ati participat in numar atat de mare! Si speram ca presiunea creata in ultima jumatate de ora nu a avut efecte negative asupra sanatatii voastre.

Dupa o discutie aprinsa cu Budau Adrian si Ristache Dragos am ajuns la cateva concluzii:

1. Ca raspuns la intrebarea topicului, am ajuns de comun acord la concluzia ca deschiderea tuturor surselor nu e cea mai buna solutie in conditiile curente. Ceea ce a ajutat majoritatea userilor buni de pe infoarena sa ajunga la un nivel decent sunt exact problemele la care au stat sa se gandeasca mult. Mi se pare ca in evolutia personala, inainte de un anumit nivel (care poate fi determinat de varsta, maturitate sau alti factori) esti tentat sa o iei pe calea usoara.
De exemplu eu, acum ceva timp, daca stiam ca o problema are solutia intr-un articol, stateam si ma gandeam maxim o jumatate de ora dupa care citeam solutia si implementam. In cele mai multe cazuri, dupa o luna nu mai stiam cum se rezolva problema. Pe cand, la problemele la care ma gandeam pentru o perioada mai lunga de timp (de ordinul orelor / zilelor), chiar daca nu ma prindeam singur, ramaneam cu ceva.
Tind sa cred ca (,) comportamentul meu era determinat de motivatia clasamentului. Da, s-a mentionat mai sus ca asta in cele mai multe cazuri este o problema personala, dar eu cred ca o problema personala care se manifesta intr-un numar mare de persoane devine implicit o problema a comunitatii.

Ceea ce ne duce la 2-a concluzie:
Deschiderea completa a surselor si clasamentul nu ar trebui sa se regaseasca impreuna pe site. Adica, generalizand, ajungem la problema mai delicata a scopului Infoarenei. Aici eu cred ca exista doua tipuri de abordari: vrem sa fim ca SGU, Timus si alte Online Judge-uri (adica probleme fara hinturi si clasament relevant) sau vrem sa fim o comunitate educationala. Fara a jigni pe nimeni, cred ca momentan infoarena e o struto-camila. Incearca sa le faca pe ambele, ies destul de bine, doar ca ar iesi si mai bine daca ne-am concentra pe una dintre cele doua.

Nu cred ca e foarte greu sa constatam ca de-a lungul timpului infoarena a migrat de la prima categorie catre a doua. Momentan e "pe drum", si sunt sigur ca o sa ajunga la un rezultat super, cu cateva mici modificari.

O scurta paranteza legata de motivatie. Wefgef are dreptate cand spune ca trebuie sa existe intrinsec, doar ca asta e o situatie ideala. Se mai intampla sa te impotmolesti, sa te demoralizezi, etc, momente in care se vede importanta factorilor externi. (un rating, un achievement sau altele).

Si pornind de aici am venit cu cateva propuneri - toate astea se refera strict la partea de arhiva, nu avem nicio treaba cu concursurile -.

Ce-ar fi daca am inlocui clasamentul arhivei cu alte metode de motivare mai eficiente?

Ce credem noi este ca problema copierii surselor / a tratarii superficiale a problemelor provine din dorinta de a fi mai sus decat X in clasament - o competitie care nu isi are locul aici. Asa ca am incercat sa gasim ceva ce ar motiva elevul sa lucreze pentru el: un sistem de achievement-uri.

Pe scurt:
Fiecare poate sa vada strict ce a rezolvat el. Exista categorii de probleme (cum sunt tag-urile acum) si nivele de dificultate. Ai optiunea de a sti sau de a nu sti in ce categorie si la ce dificultate e o problema.  Cand ai rezolvat un anumit numar de probleme dintr-o anumita categorie, primesti ceva. (un exemplu stupid ar fi titlul de Mare Maestru al Problemelor de Programare Dinamica cu Masti pe Biti). Existenta unor challange-uri: fa X probleme din categoria Y pana Miercuri. Toate sursele sunt open.

Pe mine genul acesta de provocari ma fac sa fiu mult mai entuziast decat un clasament. (poate ca e pur si simplu noutatea, dar si asta e un aspect pozitiv).
De ce s-ar rezolva problema cu sursele open? Nu o sa iti spuna nimeni "vai ce smecher esti tu, ai 100.000 de puncte". Pentru fiecare achievement obtinut o sa stii: "pe asta l-am facut pe bune, ma simt mandru de el. Pe asta l-am cam copiat, ce-ar fi sa mai lucrez la niste probleme asemanatoare? ". Nu vreau sa o dau in balarii si mai tare, dar cred ca in cazul asta constiinta ar actiona mai bine decat daca exista un clasament.

Pe cine ar influenta acest nou tip de sistem?

1. Userii noi / Incepatorii in programare: ar avea un guideline, ar sti care sunt problemele de inceput, ar face mai intai chestiile simple, ar obtine achievement-urile usoare (5 probleme rezolvare in arhiva, 3 back-uri la mai putin de jumate din limita de timp, prima problema de grafuri, etc). Fiind nou intr-un domeniu si pe un site, mi s-ar parea super cool sa am parte de asa ceva.

2. Clientii fideli: in loc sa fie motivati sa ii depaseasca pe altii, vor fi motivati sa progreseze. Poti castiga competitia cu altii copiind surse, dar nu pe cea cu tine. Teoretic stii asta oricum, dar cand ai un clasament care sa te distraga, mai uiti.

Nu stiu daca asta e o directie inspre care vrea infoarena sa se indrepte, dar mi se pare ca e o solutie.
Astept feedback de la voi, sunt curios ce puncte slabe/forte pe care noi nu le-am vazut exista.
Imi cer scuze pentru postul extrem de lung.

Stiu ca nu suna foarte realist, dar in cazul in care se va ajunge la implementarea unei chestii de felul asta, va bazati pe cel putin 3 oameni (Dragos, Adi si eu).

Incearca sa scrii asa:

fscanf(in," %c ",&c);

Adica cu spatiu inainte si dupa %c, deoarece in caz ca ai enter-uri / spatii, varianta initiala le considera caractere pentru citit, pe cand a 2-a o sa sara peste ele.

O sa pornesc de la supozitia ca Cosmin a lansat o solutie atat de drastica tocmai pentru a aprinde si a starni interes in aceasta discutie.

Limitarea locurilor pe liceu e o solutie pentru "dizolvarea" monopolului - elevi buni nu ar mai merge la ICHB/Vianu/alte licee bune din cauza fricii de a nu mai prinde nationala -, dar cu siguranta NU e o solutie pentru imbunatatirea performantelor internationale ale Romaniei. Si sper ca scopul acestei discutii este gasirea unei metode de ridicare a informaticii romanesti si nu gasirea unei metode de a ingropa liceele cu rezultate.

De ce am venit eu la ICHB? Pentru ca imi oferea alte perspective decat orice liceu din Cluj. O sa dau cateva dintre motivele mele - pe unele le constientizam din clasa a 8-a, dinainte sa vin, dar pe altele incep abia acum sa le vad.

1. Motivul evident - pregatirea la informatica.
    a) profesori mai buni decat aveam in Cluj - cred ca toata lumea e de acord ca ICHB are profesori extrem de buni, ce elev de gimnaziu / liceu care este pasionat de informatica nu ar vrea sa faca pregatiri cu fosti olimpici internationali? Din pacate motivul acesta restrange destul de mult cercul centrelor de informatica la Bucuresti. Da, exista cativa profesori excelenti si in cateva judete din tara (Craiova, Bistrita, Iasi, etc), dar majoritatea se gasesc in capitala si sunt destul de convins ca asta nu se va schimba in viitorul apropiat. (cei mai multi studenti care fac pregatiri sunt la universitate in Bucuresti, nu in alte orase ale tarii).
    b) comunitate - evident ca o sa vreau intr-un mediu in care mai sunt si altii pasionati de ceea ce imi place mie. Concurenta duce la progres, colaborarea la fel. Dar trebuie sa ai cu cine, si asta e un alt lucru pe care nu il aveam acasa, dar l-am gasit aici.

2. Aplicatiile la universitatile din strainatate
    Fiind o comunitate mare de elevi buni + multi fosti elevi acceptati la cele mai bune universitati ale lumii, informatia circula mult mai repede si mai bine. Sunt prea putine locurile din tara in care se afla tot ce este nevoie despre aplicatul inafara.

Si inca 2 motive personale:
3. Bucuresti
    Cu riscul de a imi lua multa lume in cap, o sa afirm ca in Bucuresti posibilitatile de a face orice sunt mai bune decat in celelalte orase ale tarii.

4. Internatul
    Asta este unul dintre motivele pe care nu le constientizam cand am decis sa vin aici, dar pe parcurs mi-am dat seama ca mi-a fost extrem de benefic. Te maturizeaza enorm de mult, te invata sa te descurci singur. Da, exista riscuri, dar mi se pare ca merita sa ti le asumi, pentru ca nu e chiar asa de greu sa "rezisti tentatiilor  ".

De ce am ales ICHB si nu un alt centru? (Vianu, Craiova, etc)
Simplu, pentru ca ICHB stie sa se vanda. Publicitate buna, rezultate excelente. Si cel mai important, nu te limiteaza geografic (internat). 

Cum cred eu ca s-ar rezolva problema?
Au spus-o multi inaintea mea, prin imbunatatirea calitatii studiului informaticii in alte zone ale tarii. Atat timp cat elevul bun vrea un profesor interesat si cel putin 2-3 oameni cu care sa concureze, dar nu le are la el in judet / oras / scoala, mi se pare absolut normal sa mearga undeva unde i se ofera asta.

Din pacate nu stiu cat de multi profesori de informatica buni si dornici exista prin tara, iar cu studentii e problematica treaba, din cauza ca majoritatea migreaza inspre Bucuresti. Nu cred ca exista vreunul care e atat de altruist incat sa cedeze o educatie mai buna pentru a ramane sa ii ajute pe elevii din judetul sau sa faca bine la olimpiada. E fix aceeasi situatie ca si cea cu plecatul in strainatate la universitate / serviciu, doar ca la o alta scara.

Daca ar exista continuitate si implicare constanta peste tot pe unde se face informatica la nivel inalt acum, cred ca ar fi un pasinainte. E foarte important ca liceenii mari (11-12) sa ii ajute pe cei mai mici si ca profesorii sa incerce sa mentina constant in jurul lor un grup de elevi care doresc sa faca performanta.

Sper ca parerea mea nu a deranjat pe nimeni si imi cer scuze pentru lungimea postului.

Toate cele bune,
Cezar

AIB-urile se pot folosi si pentru update/query de minim si maxim doar daca toate intervalele cu care au de a face sunt de forma 1..x. Se folosesc exact la fel ca si in cazul adunarii, doar ca se inlocuiesc operatiile de "+" cu cele de max( , ).

Update-ul arata cam asa: (poz e pozitia la care se face update-ul, val e valoarea cu care se face update)

Cod:

void update(int poz, int val) {
    int i;
    for (i = poz; i <= N; i += lsb(i)) 
        AIB[i] = max(AIB[i], val);
    
}

Query-ul merge asa (se face query pe intervalul 1..poz):

Cod:

int query(int poz) {
    int i, sol = 0;
    for (i = poz; i > 0; i -= lsb(i)) 
        sol = max(sol, AIB[i]);
    return sol;
}

Citeste putin aici, explica bine principiul dualitatii si diagramele Voronoi. Pe scurt, celula Voronoi a punctului (0, 0) reprezinta locul geometric al punctelor care sunt mai apropiate de el decat de celelalte N puncte, si are forma unui poligon convex (posibil deschis). Se poate determina in O(N log N) folosind dualizarea si o infasuratoare convexa. Sper sa iti fie de folos, daca mai ai intrebari nu ezita sa le pui!

Problema Forum se poate rezolva si cu Diagrame Voronoi (trebuie sa gasesti celula Voronoi a punctului (0, 0) si apoi pentru fiecare query sa verifici daca punctul se afla in celula). Am prezentat asta la lot, daca vrei mai multe detalii / sursa spune.

Uitati aici cateva punctaje (cumulate cu primul lot):

1. Adrian Budau - 959
2. Vlad Gavrila - 670
3. Radu Voroneanu - 652
4. Andrei Purice - 640
5. Cazacu Alex - ~580
6. Gheorghe Mihai - 572
7. Calancea Mihai - 550
8. Stan Serban - 549
9. Cezar Mocan - 510
10. Dani Posdarascu - 509
11. Tache Alexandru - ~ 450
12. Antonescu Andrei - 440
13. Teodor Pripoae - ~400
14. Poenaru Andrei - 394
15. Ciocan Andrei - ~300
16. Anca Login - 300

La ultimele punctaje eroarea s-ar putea sa fie destul de mare (pana in 50 de puncte totusi), dar clasamentul cam asa arata. Victor Ionescu si Andrei Alexandrescu nu au venit la aceasta tabara a lotului.

Calendarul apartine de forum, iar SMF (Simple Machines Forum) fiind American a venit cu cateva sarbatori default in calendar. Sa ma corecteze cineva daca gresesc