\begin{yl}{6}{Mugandatud ahel}{ahel}{1 sek / 3 sek}{100 punkti}
\emph{Idee, teostus ja lahenduse selgitus: Andres Alumets}

\begin{quote}
On antud tippude ahel pikkusega $N$, millele on lisatud üks serv mingi kahe tipu vahele. Vaja on leida iga arvu $k \in {1, 2, \ldots, N}$ jaoks, mitu sellist tipupaari leidub, mille vahel lühima tee pikkus on $k$.

Alamülesanded: Ahela pikkus kuni $100$, kuni $5\,000$, kuni $100\,000$.
\end{quote}

Vaatame võimalikke lahendusi alamülesannete kaupa.

Esimeses alamülesandes, kus $N \le 100$, mahub ajalimiiti lahendus, mille keerukus on $O(N^3)$. Sellise keerukusega on näiteks Floyd-Warshalli algoritm. Saame teha $N \times N$ tabeli ja kõigi tipupaaride vahelised kaugused välja arvutada. Pärast saab sellest tabelist iga kauguse kordused kokku lugeda. Tuleb tähele panna, et iga tipupaari tuleb lugeda ainult ühe korra. Seega õige vastuse saamiseks tuleb tabelis esinemiste arv jagada $2$-ga.

Teises alamülesandes, kus $N \le 5\,000$, mahub ajalimiiti lahendus, mille keerukus on $O(N^2)$. Selline lahendus on näiteks kõikide tipupaaride vaatlemine. Näiteks vaatame tipupaari $a, b$, kus $a < b$. Kui mõlemad on väiksemad lisatud serva väiksemast otspunktist, siis nende vaheline kaugus on $|b-a|$. Samamoodi ka siis kui mõlemad on suuremad lisatud serva suuremast otspunktist. Kui $a$ on väiksem kui lisatud serva väiksem otspunkt ja $b$ on suurem kui lisatud serva suurem otspunkt, siis läbib lühim tee kindlasti lisatud serva ja on võimalik leida kaugus tipust $a$ lisatud servani ja lisatud servast tipuni $b$. Ülejäänud juhud on sellised, kus vähemalt üks kahest tipust on graafi ainukesel tsüklil. Siis saab leida kaugused kui minna mööda üht tsükli poolt või mööda teist ja võtta nendest miinimum. Sellise lahendusega peaks kätte saama $50$ punkti.

Kolmandas alamülesandes, kus $N \le 100\,000$, on oodatav lahendus keerukusega $O(N)$. Jätkame ideed, kus jagame graafi osadeks. Kindlasti on selleks jagamiseks mitmeid võimalusi, kuid näidislahenduses jagame näiteks nii: ütleme et uus serv on tehtud tipust $X$ tippu $Y$, kus $X < Y$. Siis esimene osa on tipud $1, 2, \ldots, X$, teine $Y, \ldots ,N$ ja kolmas $X+1, X+2, \ldots, Y-1$.

\begin{center}
\begin{tikzpicture}[scale=0.6, every node/.style={circle, draw, minimum size=14mm}]
  \draw (0, 0) node (1) {$1$};
  \draw (4, 0) node (2) {$2$};
  \draw (8, 0) node (Xm) {$X-1$};
  \draw (12, 0) node (X) {$X$};
  \draw (16, 0) node (Y) {$Y$};
  \draw (20, 0) node (Yp) {$Y+1$};
  \draw (24, 0) node (N) {$N$};

  \draw (10, 3) node (Xp) {$X+1$};
  \draw (18, 3) node (Ym) {$Y-1$};

  \draw (1) -- (2);
  \draw[dashed] (2) -- (Xm);
  \draw (Xm) -- (X) -- (Y) -- (Yp);
  \draw[dashed] (Yp) -- (N);
  \draw (X) -- (Xp);
  \draw[dashed] (Xp) to[out=60, in=120] (Ym);

  \draw (Ym) -- (Y);
\end{tikzpicture}
\end{center}

Paneme tähele et esimene ja teine osa moodustavad ühe ahela. Olgu selle ahela pikkuseks $m$. Paneme tähele et tipupaare kaugusega $1$ on seal $m-1$, paare kaugusega $2$ on $m-2$ jne. Seega saame $O(N)$ ajas leida iga kauguse kohta nende arvu.

Nüüd vaatame juhtu, kus üks tipp on esimeses osas ja teine kolmandas. Lihtsuse mõttes võib kolmandasse ossa lisada ka tipu $Y$. Siis igal esimese osa tipul on mingil kaugusel kolmandas osas alati kas $2$ või $0$ tippu (kui kaugus on kas liiga suur või liiga väike). Erijuht on siis, kui tsükli pikkus on paaritu. Siis on ühe kauguse puhul kolmandas osas ainult $1$ tipp.

Seega idee on teha esimese osa peal libisev aken, kus kõigil aknas olevatel tippudel on mingil kaugusel vähemalt üks tipp kolmandas osas. Algul on aknas ainult tipp $X$ ja kaugus $1$. Iga järgmise kaugusega liigub akna väiksem ots tipu $1$ poole ja ülemine ots jääb paigale. Ülemine ots hakkab vähenema siis, kui ülemise otsa juures oleval tipul kolmandas osas enam vaadeldaval kaugusel ühtegi tippu pole. Nii saame lihtsalt akna pikkuse järgi õige kaugusega paaride arvu kokku lugeda.

Sarnane lahendus on ka teise ja kolmanda osa kohta.

Kui mõlemad tipud on kolmandas osas, siis tsükli peal on igal tipul täpselt $2$ paarilist iga kauguse kohta mis on väiksem kui pool tsükli pikkusest. Seega ka nende kokku lugemine on kiiresti tehtav.

Ülesandes on lisaks veel mõned tehnilised keerukused. Lohakalt lahendades võib juhtuda et mõnda paari loetakse mitmekordselt. Seega peab pidevalt ka seda jälgima ja vajadusel mõne tipu mitmekordselt loetud paarilised maha lahutama.

\end{yl}
