[subarborele minim]

Grupul lui Tanaka va vizita doar subarborele minim ce conţine toate hotelurile lor

Ce se intelege prin subarbore minim? Mi se pare putin ambiguu. Se refera la notiunea clasica de subarbore (fixezi o radacina si alegi subarborele minim care iti contine toate cele K noduri) sau se refera la multimea minimala conexa de noduri care iti contine toate cele K noduri?

De exemplu, pentru al doilea exemplu din enunt, daca aleg nodurile {2, 3, 4}, "subarborele minim" mai contine si alte noduri sau le va contine doar pe acestea?

Mersi frumos 

Puteti sa puneti aici un link de la monitorul de evaluare unde se vad doar sursele de la runda?

Testele sunt grupate?

Nu, la ONI sunt puse limite la dimensiunile surselor, deobicei de 10kb.

Cand se vor pune problemele in arhiva? 

[Spoilers ahead!]

Lista mea:

Spoilers ahead!

1. NoGameNoLife - The Final Stage -> pentru smenul cu rularea programului cat timp nu ia TLE, super util si in alte cazuri   (http://www.infoarena.ro/problema/nolife)

2. Tri -> cred ca a fost unul dintre cele mai puternice sentimente de "mind-blown" pe care le-am avut cand mi-a fost explicata metoda de rezolvare ( cea care nu necesita structuri de date )   (http://www.infoarena.ro/problema/tri)

3. Gravity -> dijkstra pe costuri mici..subtil (http://www.infoarena.ro/problema/gravity)

4. Import -> mi s-a parut super faina metoda de a rezolva un sistem de inecuatii de genul x - y <= k (k constant) cu Bellman Ford (http://www.infoarena.ro/problema/import)

5. Hide and Seek Game -> problema care m-a facut sa realizez utilitatea ciclilor din cadrul unei permutari (http://www.infoarena.ro/problema/hideandseek)

6. Arbfind -> idee inedita de rezolvare (http://www.infoarena.ro/problema/arbfind)

7. Fantasy -> pur si simplu mi-a placut (http://www.infoarena.ro/problema/fantasy)

8. Cowfood -> (http://www.infoarena.ro/problema/cowfood)

9. Unlock -> misto ideea de a folosi paduri de multimi disjuncte care suporta si operatia de undo (http://www.infoarena.ro/problema/unlock)

10. Rangemode -> pentru algoritmul lui Mo, destul de intalnit acum (http://www.infoarena.ro/problema/rangemode)

Testul 15 este gresit. Se spune ca sunt 5 teste, insa sunt date apoi doar datele pentru 4 teste..

Cand o sa fie problemele adaugate in arhiva?

Mi se pare stransa limita de timp...sursa oficiala ia abia 70p. 

La date de iesire presupun ca este cate o linie pentru fiecare test in parte. (ma refer la enunt)

Iti dai seama ca nu se poate face asta din exemplu.

Eu stiu ca am vazut pe prima pagina de acum 2 zile. E adevarat ca pagina concursului nu fusese creata de atunci, dar era acolo.

La explicatii, varianta 4, ultima operatie nu ar trebui sa fie [1,2]? Operatia [1,4] nu ar trebui sa fie valida fiindca cutia 4 este goala. 

Presupunand ca fiecare din cei doi joaca optim

Pe cazul din exemplu se intampla ceea ce este scris la explicatii, mai jos de enunt.

Ideea este ca primul jucator vrea sa maximizeze diferenta, iar cel de-al doilea urmareste sa o minimizeze, asta inseamna ca "amandoi joaca optim".

Cred ca limita initial fusese bine pusa, insa ultimele 3 pagini sunt cu surse care luau TLE intentionat ca sa blocheze eval-ul, si de aia au modificat limita la 0.01.

E pusa, dar cu alt nume: http://www.infoarena.ro/problema/crescator3

M-am uitat pe sursa ta.
Problema la tine aparea la final

Cod:

1LL * (1 << bits)

...care de fapt nu iti calculeaza pe long long.
Ca sa iti mearga, schimba cu

Cod:

(1LL<<bits)

La problema asta nu se poate submita, apare "invalid task ID" in mai multe locuri. 

E destul de greu pentru cineva sa iti ia sursa si sa verifice unde este greseala. Ia mult timp, mai ales datorita faptului ca fiecare are un stil de codare diferit.

Cel mai bine e sa iti generezi teste mici si sa faci debug pe sursa pas cu pas ( nu sa vezi numai daca rezultatul final e OK ). Vei afla unde e greseala mai repede si te va ajuta si in concurs mult mai mult. Bafta!

Cod:

for(long long j = i * i; j <= DIM; j += i) {
                CE[j] = 1;
            }

In codul tau iterezi cu j-ul pana la DIM, ceea ce e gresit, fiindca containerul bitset e indexat de la 0 la DIM - 1, si atunci cand ajungi exact in DIM, accesezi aiurea, ceea ce conduce la greseli. Acelasi lucru il faci si in sursa cu char, dar aparent acolo nu are aceleasi urmari.

nume de variabile aiurea
++i  in loc de i++  deoarece e mai rapid ( chestia asta ma zgarie cel mai rau pe ochi )
for-uri descrescatoare, deoarece comparatia cu 0 e mai rapida deoarece, chip-ul nu are curent (nu stiu cati sunteti familiari cu asta dar la un moment dat avea un trend asecendent) dar e ca si i++ si ++i, tot un mit
cod de mai multe linii puse pe o singura linie ( sa fie sursa mai mica )

Tot ce ai zis tu mai sus tine de preferinta fiecaruia. Nu vad nimic gresit in a alege sa le folosesti. Vorbim de programare competitiva in primul rand.

Si pana la urma daca se fac sursele libere fiecare are dreptul sa se uite prin ele si sa aleaga un stil care ii place, si care simte ca il ajuta cel mai bine atunci cand vine vorba de probleme pentru concursuri. Chiar mi se pare folositor sa vezi mai multe tipuri de a coda si sa poti face o comparatie intre ele.


 

Mi se pare o dezbatere foarte buna si vreau sa imi las si eu parerea aici.

Privind inapoi cu cativa ani si la modul cum ma pregateam pe atunci, imi dau seama ca solutiile oficiale si sursele celorlalti au fost niste elemente care pe mine m-au ajutat enorm.

Pregatirea pentru olimpiade mi-am inceput-o pe campion, care mi-a placut foarte mult la inceput tocmai datorita solutiilor la probleme pe care le oferea, plus primul test pe care solutia ta nu il trecea. Dupa un timp a venit vremea sa fac tranzitia la infoarena, care in judetul meu nu era tocmai populara, fiindca erau putini cei care chiar faceau algoritmica la nivel competitiv. Din aceasta cauza si ajutorul pe care il primeam de la profesori sau colegi mai mari era minim si am fost fortat de imprejurari sa devin autodidact si sa incep sa invat cat mai multe pe cont propriu.

Incepand de la stadiul in care nici la problemele cele mai usoare nu stiam rezolvarile de 100 si parcurgeam diverse teme de pregatire intr-o ordine destul de haotica, am inceput sa ma axez foarte tare pe articole de rezolvare ( la problemele care aveau ) si pe surse oficiale sau cele de la problemele open-source. Recunosc ca nu era tocmai sanatoasa atitudinea pe care o aveam, si anume sa ma uit pe solutii si surse daca nu imi vine ideea in 20 de minute, insa la momentul respectiv m-a ajutat foarte mult. Am invatat atat idei noi, cat si metode diverse de implementare( stateam ore intregi sa ma uit prin surse numai ca sa imi gasesc un tipar de cod care sa imi placa si pe care sa il adopt ), pe care altfel nu as fi avut de unde altundeva sa le asimilez.

Pe scurt, daca toate sursele ar fi libere la probleme, ar fi un avantaj enorm pentru cei care sunt dispusi sa lucreze si sa se informeze pe cont propriu, si cred ca sunt destul de multi aici care s-au regasit in aceasta situatie.

Cat despre cei care s-ar folosi de asta numai ca sa triseze si sa copieze sursele altora, vor ajunge la un moment dat sa realizeze ca nu este o tactica deloc sanatoasa. Pana la urma, dupa cateva concursuri nereusite la rand, incepi sa te gandesti ce este gresit in metoda de pregatire ... si brusc iti aduci aminte de sursele pe care le trimiteai copy-paste.

Just my opinion.

Poate explica cineva cum se facea OneOuts de 100?

Nu stiu unde altundeva sa postez, asa ca intreb aici: cam cand se estimeaza ca se vor afisa rezultatele?