Sistem nejednačina

Označimo sa ~i_1, i_2, ... , i_m~ indekse (promenljive) ugnježdenih petlji.

Svaki put kada se telo najdublje petlje izvrši, znamo da su već zadovoljeni neki uslovi za ove indekse, tačnije za svaki indeks ~i_k~ znamo da važi ~max \{ i_{j}(j \in P_{k})\} \leq i_k \leq min \{ i_{t}(t \in Q_{k})\}~

Odnosno, odatle vidimo da važi ~i_j \leq i_k~ za ~\forall j \in P_k~ kao i ~i_k \leq i_p~ za ~\forall p \in Q_k~ .

Takođe iz uslova zadatka znamo da važi i ~1 \leq i_k \leq n~.

Ovime smo dobili sistem nejednačina po promenljivama ~i_1, ..., i_m~, a broj rešenja tog sistema nejednačina je upravo traženo rešenje.

Slučaj kada su sve promenljive različitih vrednosti

Primetimo da dok brojimo rešenja nisu mnogo bitne tačne vrednosti promenljivih (kojih može biti mnogo, odnosno od ~1..n~), već samo relativan redosled promenljivih. Ukoliko pogledamo slučaj kada su vrednosti svih promenljivih različite, nama je zapravo bitan broj permutacija Perm brojeva od ~1..m~ za koje može da važi: ~i_{Perm_1} < i_{Perm_2} < i_{Perm_3} < ... < i_{Perm_m}~ Odnosno koje se uklapaju u dati sistem nejednačina.

Ukoliko je broj ovih permutacija jednak ~S~, ukupno rešenje bi bilo ~S * {n \choose m}~ zbog toga što možemo izabrati ~m~ različitih brojeva od ~1..n~ za rešenja za svaku validnu permutaciju.

Uopšteni slučaj

Pošto neke promenljive mogu da budu jednake, potrebno je da posmatramo opšti slučaj. Pretpostavimo da ćemo imamti ~R~ različitih brojeva u rešenju (svakako važi da je ~1 \leq R \leq m~). Svakoj promenljivoj ~i_k~ ćemo dodeliti neku vrednost ~V_{i_k}~ od ~1..R~. Takođe, po pretpostavci, svaki od brojeva od ~1..R~ će biti dodeljen bar jednoj promenljivoj. One promenljive kojima je dodeljen isti broj označavaju da su one jednake u krajnjem rešenju, a vrednost brojeva označava relativan raspored između promenljivih. Odnosno, imamo da je: ~i_{p_1} (\forall p_1 : V_{p_1} = 1) < i_{p_2} (\forall p_2 : V_{p_2} = 2) < ... < i_{p_r} (\forall p_r : V_{p_r} = R)~

Takođe, ~i_k = i_j \iff V_{i_k} = V_{i_j}~

Za ovakve vrednosti ~V~ kažemo da su validne ukoliko tako dobijene nejednačine uklapaju sa datim sistemom nejednačina.

Za svako ~R~ (od ~1..m~) ćemo izbrojati koliko ima validnih rasporeda ~V~. Taj broj je opet potrebno pomnožiti sa ~n \choose R~, slično kao i u prvom slučaju.

DP nad skupovima

Pošto je ~m~ malo (do 15), ove rasporede možemo brojati dinamičkim programiranjem nad skupovima.

Gledajmo podskup nekih promenljivih ~T \subset \{i_1, i_2, .... i_m\}~. Neka je ~S[T][R]~ broj validnih rasporeda vrednosti ~V~ nad ovim skupom promenljivih ~T~, gde će svaka vrednost biti najviše ~R~. Izaberimo neki podskup ~X \subset T~. Tom podskupu promenljivih ćemo svima dodeliti istu vrednost 1, što označava da će one biti manje od ostalih iz tog podskupa, a iste međusobno. Ostalima (odnosno podskupu ~Y = T \setminus X~) ćemo dodeliti veće vrednosti (~2..R~), a bitno je primetiti da je broj tih rasporeda za skup ~Y~ onda isti kao ~S[Y][R-1]~.

Ono što treba da pazimo je i da se to uklapa sa sistemom nejednačina, odnosno da sve promenljive u ~X~ smeju da budu manje od svih promenljvih u ~Y~.

To ćemo raditi tako što ćemo, pre svega, za svaku promenljivu ~i_k~ pamtiti skup ~L_{i_k} = \{i_t, i_t \leq i_k\}~, odnosno skup promenljivih koje po datom sistemu moraju da budu manje ili jednake od ~i_k~. Takođe, za svaki podskup ~B \subset \{i_1, i_2, ..., i_m\}~ možemo da izračunamo skup ~LU_B = \bigcup L_{i_k}, i_k \in B~, odnosno uniju svih promenljivih koje po sistemu su potrebne da budu manje od neke promenljive iz ~B~.

Ovime dobijamo da za izabran skup ~X~ (i time dobijen skup ~Y = T \setminus X~) mora da važi ~LU_X \cap Y = \emptyset~, da bi sistem i dalje ostao zadovoljen.

Konačno, dobijamo rekurzivnu formulu: ~S[T][R] = \sum_{X \subset T;\;Y=T \setminus X;\; LU_X \cap Y = \emptyset} S[Y][R-1]~

Kao i ukupno rešenje: ~\sum_{r=1}^{m} S[\{i_1, i_2, ..., i_m\}][r] * {n \choose r}~

Ukoliko pažljivo kucamo operacije nad skupovima i podskupovima, ukupna složenost ovog rešenja je ~O(m3^m)~.

Zadatak je preuzet sa ~\texttt{Moscow}~ ~\texttt{Autumn}~ ~\texttt{Workshop}~ ~\texttt{2019}~ ~\texttt{Day}~ ~\texttt{2}~, takmičenje ~\texttt{In}~ ~\texttt{A}~ ~\texttt{Galaxy}~ ~\texttt{Far}~ ~\texttt{Far}~ ~\texttt{Away}~