945 Tabara2

[•raduzer]

Aici puteti discuta despre problema Tabara2.

[•jupanubv92]

Cand o sa putem vedea si noi solutia oficiala la problema asta?

[•raduzer]

Cel tarziu maine.  

[LE]: Am adaugat si solutia la problema asta. Poti accesa pagina apasand aici.

[•jupanubv92]

Mersi fain pentru solutie . 

[•Mishu91]

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.

[•alexei]

Foarte faina problema! 

@Mishu91:
"# Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie (direct sau indirect)." 

[•raduzer]

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.

[•Florian]

Merge scazuta limita la 0.2 secunde. Intra lejer. 

[•stocarul]

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.

[•Florian]

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)
        {
               // unesc componenta lui i cu comp lui j
               tmpi = find(i), tmpj = find(j);
               if(tmpi != tmpj)
                     join(tmpi, tmpj);
        }
else
            {
               L[j] = i; // sarcina j se executa la locatia i
                if (P[i] < S[tmpi = find(j)])
                {
                    P[i] = S[tmpi];
                    update(1,1,N,i,P[i]);
                }
            }

[•raduzer]

@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.

[•pepsiM4A1]

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'.