h1. 'Holiday':problema/holiday
h1. 'Autobuze2':problema/autobuze2
Plecand incepand cu ziua $A$ si mergand din $X$ in $X$ zile , Antonia va fi in vacanta in zilele de forma $A + X * K (K - numarul vacantei). Similar, Antonio este in vacanta in zilele de tipul $B + Y * T (T - numarul vacantei). Numarul maxim de intalniri dintre cei $2$ are loc daca Antonia il vede pe Antonio de fiecare data cand merge in vacanta. Acest lucru se rescrie matematic astfel:
* $Se garantează că între oricare două staţii consecutive din traseul unui autobuz există o stradă directă.$
* $A + X * K = B + Y * T1 (Antonia il vede in vacanta K)$
* $A + X * (K + 1) = B + Y * T2 (Antonia il vede si in vacanta K+1)$
* $Se garantează că între A ~Ki~ şi A ~1~ există o stradă directă, pentru orice i, 1 ≤ i ≤ B.$
Avem:
Având în vedere precizările din enunţul problemei, putem crea un nou graf care folosindu-ne doar de staţiile prin care trece fiecare autobuz. Cum traseul parcurs de un autobuz este: A ~1~, A ~2~, ..., A ~K~, A ~1~, A ~2~, etc., vom conecta între ele oricare două staţii consecutive din acest traseu printr-o muchie în noul graf. Vrem să pornim din nodul $1$ şi să ajungem în nodul $N$, deci vom porni o parcurgere în lăţime din nodul $1$, ţinând pentru fiecare nod $i$ parcurs până acum:
* $X = Y * (T1 – T2), de unde X divizibil cu Y$
* $X * K = B – A + Y * T1, de unde B - A e divizibil cu Y$.
* $d[i] = numarul de noduri (staţii) parcurse din nodul 1 pana in nodul i$
Deci $Y$ e un divizor comun al lui $X$ si $B – A$. Ne intereseaza cel mai mare $Y$ cu aceasta proprietate deci intuim ca $Y = cmmdc(B - A, X)$ (notat cu $D$).
Cum $A + X * K = B + D * ( (A - B) / D + X * K / D) )$, inseamna ca pentru $Y = cmmdc(B - A, X)$ fiecare vacanta a Antoniei va fi petrecuta alaturi de Antonio.
In concluzie, este suficient sa calculam $cmmdc(B - A, X)$.
h1. 'Autobuze2':problema/autobuze2
* $Se garantează că între oricare două staţii consecutive din traseul unui autobuz există o stradă directă.$
* $Se garantează că între A ~Ki~ şi A ~1~ există o stradă directă, pentru orice i, 1 ≤ i ≤ B.$
Având în vedere precizările din enunţul problemei, putem crea un nou graf care folosindu-ne doar de staţiile prin care trece fiecare autobuz. Cum traseul parcurs de un autobuz este: A ~1~, A ~2~, ..., A ~K~, A ~1~, A ~2~, etc., vom conecta între ele oricare două staţii consecutive din acest traseu printr-o muchie în noul graf. Vrem să pornim din nodul $1$ şi să ajungem în nodul $N$, deci vom porni o 'parcurgere în lăţime':problema/bfs din nodul $1$, ţinând pentru fiecare nod $i$ parcurs până acum:
* $d[i] = numarul de noduri (staţii) parcurse din nodul 1 pana in nodul i$
Răspunsul se va găsi în $d[N]$. Dacă nu am putut ajunge în nodul $N$, îl vom încuraja pe Antonio să o invite pe Antonia la un suc.
h1. 'Litere2':problema/litere2
h1. 'Treesmen':problema/treesmen
Vom face o liniarizare a arborelui, cu ajutorul căreia vom efectua eficient cele două operaţii. Soluţia se bazează pe prima idee care ne vine în minte, adică, pentru prima operaţie facem update pe intervalul $[first[stramos], first[node]]$ şi pentru a doua căutam ce valoare avem pe poziţia $first[node]$; dar, s-ar putea, ca la update să avem noduri care nu se află pe lanţ dar apar şi în interval.
Plecând de la această observaţie vom ajunge la altă observaţie: aceste noduri vor avea $first-ul si last-ul$ incluse în $[first[stramos], first[node]]$. Astfel putem defini:
* $last[node] = suma valorilor când node nu apare pe lanţ.$
Făcând această observaţie răspunsul pentru un query va fi $valoarea de pe poziţia first[node] - valoarea de pe poziţia last[node]$. Update-ul e o progresie arimetica, aşa că, nodul $X$ o să crească cu valoarea $p + (nivel[X] - nivel[stramos])*r.$ Dacă desfacem paranteza şi grupăm termenii convenabil obţinem $p-nivel[stramos]*r + nivel[X]*r$. Astfel, problema se rezumă la a face update pe un interval cu o valoare $X$; ne putem folosi de arbori de intervale sau arbori indexati binar pentru a face acest lucru.
Complexitate $O(M * log N).$
==include(page="template/monthly-2014/footer")==
