|
Titlul: 945 Tabara2 Scris de: Radu Zernoveanu din Noiembrie 15, 2009, 15:14:39 Aici puteti discuta despre problema Tabara2 (http://infoarena.ro/problema/tabara2).
Titlul: Răspuns: 945 Tabara2 Scris de: Popescu Marius din Noiembrie 16, 2009, 08:02:51 Cand o sa putem vedea si noi solutia oficiala la problema asta?
Titlul: Răspuns: 945 Tabara2 Scris de: Radu Zernoveanu din Noiembrie 16, 2009, 10:16:13 Cel tarziu maine. :)
[LE]: Am adaugat si solutia la problema asta. Poti accesa pagina apasand aici (http://infoarena.ro/dot-com/2009/solutii/runda-1). Titlul: Răspuns: 945 Tabara2 Scris de: Popescu Marius din Noiembrie 16, 2009, 13:19:27 Mersi fain pentru solutie . =D>
Titlul: Răspuns: 945 Tabara2 Scris de: Andrei Misarca din Noiembrie 16, 2009, 20:05:13 Am o nelămurire de care m-am lovit și în timpul concursului, și nu m-am prins nici din articol. La oprațiile de tip 2 updatez în arborele de intervale cu maximu poziției respective până în acel moment. Dar cum fac să updatez când se schimbă maximul sarcinilor pe care le pot face dintr-o poziție în urma update-ului de tip 1. Cum este în exemplu, cum voi updata că plecând din 2, pot face o sarcină cu valoare 4, întrucât în momentul în care am updatat în arbore valoarea pentru poziția 2, maximul era 3.
Titlul: Răspuns: 945 Tabara2 Scris de: Iacob Radu din Noiembrie 16, 2009, 20:57:58 Foarte faina problema! :D
@Mishu91: "# Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie (direct sau indirect)." :) Titlul: Răspuns: 945 Tabara2 Scris de: Radu Zernoveanu din Noiembrie 17, 2009, 10:48:55 Atunci cand ai un update de tipul 1, gasesti radacinile multimilor din care fac parte nodurile i si j si tragi muchie intre ele astfel incat una din ele va deveni radacina noii multimi formate. Tot timpul tii in radacina maximul din multime. Daca aceasta radacina este o locatie (un nod din cele N), atunci faci update pe arborele de intervale. Datorita precizarii "Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie (direct sau indirect).", esti sigur ca maxim 1 din radacinile multimilor din care fac parte i si j (initial) va fi o locatie.
Titlul: Răspuns: 945 Tabara2 Scris de: Florian Marcu din Noiembrie 17, 2009, 14:24:24 Merge scazuta limita la 0.2 secunde. Intra lejer. :ok:
Titlul: Răspuns: 945 Tabara2 Scris de: Cosmin-Mihai Tutunaru din Noiembrie 20, 2009, 18:07:33 Am făcut și eu o soluție la problema asta, însă nu îmi intră în timp pe testul 8.
Am trimis o sursă fără efectuarea apelurilor pe arborele de intervale, și tot nu se incadrează în timp. Deci, înseamnă că problema este la mulțimile disjuncte. Am folosit optimizările de la mulțimi disjuncte din arhiva educatională. Voi ați mai folosit și alte optimizări? Mulțam. Titlul: Răspuns: 945 Tabara2 Scris de: Florian Marcu din Noiembrie 21, 2009, 10:00:41 Mi-e mi-a intrat lejer in timp cu cele doua euristici din educationala [ compresia si faza cu inaltimile ]. O optimizare minora ar fi ca la instructiunea U 1 sa nu mai faci joinul daca i si j se afla deja in aceeasi componenta. De asemenea, updateul pe arborele de intervale (in cazul U 2) nu are rost sa-l mai faci daca P[ i ] ( punctajul maxim obtinut daca pleci din locatia i) este mai mare decat S [ find(j) ] ( punctajul maxim obtinut din componenta lui j ).
Cod: if(instr == 1) Titlul: Răspuns: 945 Tabara2 Scris de: Radu Zernoveanu din Noiembrie 28, 2009, 17:09:22 @stocarul: M-am uitat putin pe sursa ta si am impresia ca nu memoizezi pe update la multimi... Incearca sa memoizezi ca sigur de aici iei TLE. :wink:
Titlul: Răspuns: 945 Tabara2 Scris de: Ozturk Arif din Iulie 28, 2017, 14:46:09 Ca sa nu va chinuiti ca mine, pentru cei ce citesc 2 caractere(caracterul de newline apoi inca un caracter pentru a obtine tipul de operatie), nu faceti asta. Banuiesc ca nu toate liniile se termina cu '\n'.
|