Bazandu-ne pe aceeasi observatie ca si la solutia anterioara, putem identifica componentele conexe din graful initial, folosind doar muchiile ce au cost $0$. Astfel, putem crea un nou graf, avand ca noduri componentele conexe identificate. Apoi, vom trage muchiile ce au cost $1$ pentru a uni aceste componente conexe intre ele. Deci, problema se reduce acum la gasirea unui drum de lungime minima intre componenta conexa in care se afla nodul $1$ si cea in care se afla nodul $N$. Aceasta lungime minima se gaseste foarte usor cu o parcurgere in latime.

h2. 'Frumoasa':problema/frumoasa
 
h4. $Solutie 1: O(N) - 40 puncte$
 
In mod evident, atunci cand $P >= 26$ raspunsul va fi $0$, deoarece avem doar $26$ de caractere la dispozitie si aranjand literele in cel mai rau caz $abc...z$, nu mai avem o a $27$-a litera pentru a o adauga la sfarsit. Prin urmare, vom considera doar cazul in care $P < 26$:
 
Pe prima pozitie putem pune $26$ de litere, pe a $2$-a pozitie putem pune orice litera in afara de cea de pe prima pozitie, in total $25$; Momentan putem avea $26 * 25$ de siruri de lungime $2$; Pe a $3$-a pozitie putem pune orice litera, excluzandu-le pe cele de pe primele $2$, deci $(26 - 2) = 24$; etc. Observam rationamentul: pe a $i$-a pozitie putem pune $(26 - i + 1)$ litere, $1 <= i <= min(P, N)$.
 
Fie $SOL = (P + 1) * (P + 2) * ... * 26$
 
Avand $SOL$ posibilitati de a obtine sirul format din $P$ litere, atunci cand o adaugam pe a $(P + 1)$-a ne vom asigura doar de faptul ca litera pe care o punem la final sa nu se afle din ultimele $P$, deci solutia noastra se va actualiza : $SOL = SOL * (26 - P)$; Continuam acest procedeu pana cand completam toate cele $N$ pozitii.
 
h4. $Solutie 2: O(logN) - 100 puncte$
 
Ne vom baza pe acelasi rationament ca si in solutia anterioara. Dupa ce completam primele $P$ pozitii, observam ca inmultim solutia noastra cu $(26 - P)$ de fiecare data. Dupa completarea celor $N$ pozitii, solutia noastra a fost inmultita cu $(26 - P)$ de $(N - P)$ ori. In concluzie, putem calcula $(26 - P) ^ (N - P)$ in timp logaritmic, reducand complexitatea la $O(log(N))$.
 

h2. 'Autobuze':problema/autobuze
h4. $Solutia 1: O(N^2^) - 50 puncte$