Holiday

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:

  • 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)

Avem:

  • X = Y * (T1 – T2), de unde X divizibil cu Y
  • X * K = B – A + Y * T1, de unde B - A e divizibil cu Y.

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

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

Litere2

  • Două cuvinte fac parte din acelaşi grup dacă sunt formate din aceleaşi litere, repetate de oricâte ori.

Vom lua astfel fiecare cuvânt în parte şi vom marca toate cele 26 litere ale alfabetului englez ('a' - 'z') cu 1, dacă litera apare în cuvânt respectiv cu 0, dacă nu apare. Vom obţine astfel un şir binar de lungime 26. Putem privi acest şir binar ca fiind un număr scris în baza 2. Putem transforma acest număr în baza 10, reformulând afirmaţia iniţială astfel:

  • Două cuvinte fac parte din acelaşi grup dacă numărul astfel obţinut asociat celor două cuvinte este acelaşi.

Deci, numărul de grupuri va fi egal cu numărul de valori distincte asociate numerelor. Pentru a determina acest număr ne vom folosi de o structură de date tip Hash sau de o sortare (aceasta fiind teoretic, soluţia de complexitate mai mare).

Timpul de execuţie al acestei probleme se putea mări destul de uşor dacă în program se foloseau elemente din STL sau tipul de date string, care se miscă mai lent în practică.

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