Analiza problema

Pravolinijsko rešenje se dobija tako što se utakmice numerišu, npr. brojevima od $0$ do $N\cdot M - 1$ (ako su lige numerisane brojevima od 1 do $N$, a utakmice u okviru svake lige brojevima od 1 do $M$, onda će utakmica $j$ iz lige broj $i$ biti numerisana brojem $(i-1)\cdot M + (j-1)$) i nakon toga svaki tiket posmatra kao podskup skupa $\{0, 1, 2, ..., N\cdot M - 1\}$. Primetimo da ne mora svaki podskup skupa $\{0, 1, 2, ..., N\cdot M - 1\}$ predstavljati ispravan tiket: može se desiti da je iz nekih liga izabran nedozvoljen broj utakmica. No bez obzira na to, podskupovi se mogu reprezentovati pomoću celih brojeva između 0 i $2^{N\cdot M}-1$. Svaki broj iz tog opsega se može zapisati u binarnom brojnom sistemu sa najviše $N\cdot M$ cifara (bitova). Ako zapis ima manje od $N\cdot M$ cifara dopuni se nulama (sa leve strane). Cifra nula na mestu određene težine označava da utakmica čija se oznaka poklapa sa težinom nije izabrana u podskup (na tiket), a cifra 1, da je odgovarajuća utakmica izabrana u podskup (na tiket). Prema tome, potrebno je od broja formirati tiket, proveriti da li je tiket ispravan (validan), ako jeste, odrediti dobitak i dodati na zbir dobitaka. Složenost ovog rešenja je $\Theta(N\cdot M \cdot 2^{N\cdot M})$. Ovo predstavlja rešenje podzadatka 1.

Podzadatak 3 se takođe može rešiti na poseban način. Pretpostavimo radi pojednostavljenja da imamo samo dve lige. Iz svake lige je moguće uzeti po jednu utakmicu, a dobitak se računa kao proizvod kvota za izabrane utakmice i bonusa za tiket sa dve utakmice. Za svaki tiket će bonus biti isti (jer svaki tiket ima tačno dve utakmice), pa se zbog toga mogu prvo izračunati samo proizvodi kvota za tikete, sabrati i na kraju pomnožiti sa bonusom. Kao što smo rekli, ispravne tikete čine sve kombinacije sastavljene od po jedne utakmice iz obe lige. Zbog distributivnosti množenja u odnosu na sabiranje, zbir proizvoda kvota za sve moguće tikete će biti jednak proizvodu zbira kvota za prvu ligu i zbira kvota za drugu ligu. Ovo se može poopštiti i na slučaj kada postoji više od dve lige, pa se zbir svih dobitaka može odrediti tako što se pomnože zbirovi kvota za sve lige i to na kraju pomnoži sa bonusom (uvek isti broj - broj odigranih utakmica je jednak broju liga). Složenost ovog rešenja je $\Theta(N\cdot M)$.

Opišimo rešenje koje "pokriva" sve podzadatke. Pretpostavimo opet da imamo samo dve lige. Ako je dozvoljeno iz prve lige uzeti $k_1$ utakmica, a iz druge lige $k_2$ utakmica, onda se bilo koji podskup od $k_1$ utakmica iz prve lige može kombinovati sa bilo kojim podskupom od $k_2$ utakmica iz druge lige, a dobitak će se računati kao proizvod kvota izabranih utakmica i bonusa za $k_1+k_2$ odigranih utakmica. Kako je bonus uvek isti, može se opet računati samo zbir proizvoda kvota, pa na kraju dobijeni zbir pomnožiti sa bonusom. Zbog distributivnosti, zbir proizvoda se može dobiti tako što se saberu svi proizvodi od po $k_1$ kvota za prvu ligu, odnosno svi proizvodi od po $k_2$ kvota za drugu ligu i na kraju ta dva zbira pomnože. Ako bi bilo više od dve lige, onda bi se opet zbirove proizvoda (sa istim brojem odigranih utakmica) za pojedine lige množili i nakon toga množili sa odgovarajućim bonusom . Prema tome, potrebno je za početak za svaku ligu $i$ i svaku vrednost $j\in\{1, 2, ..., M\}$ odrediti zbir svih proizvoda kvota za tačno $j$ utakmica odigranih u ligi $i$ (označimo te zbirove sa $pr_{ij}$).

Izraze $pr_{ij}$ ćemo izračunati koristeći dinamičko programiranje. Neka je $pr_{i,j}^{(k)}$ zbir svih proizvoda kvota od tačno $j$ utakmica iz lige $i$, pri čemu svi podskupovi sadrže samo utakmice sa rednim brojevima između 1 i $k$ (naravno ne nužno sve). Tada će $pr_{i,j}^{(M)}$ biti zbir svih mogućih proizvoda kvota od po $j$ utakmica u ligi broj $i$. Lako se može zaključiti da je $None$ pr_{i,j}^{(0)}= $$\begin{cases} 1, &\text{ako je }j=0\ 0, &\text{ako je }j > 0 \end{cases}$$ . $None$

Što se tiče zbira svih proizvoda kvota za tačno $j$ utakmica gde je svih $j$ utakmica iz skupa $\{1, 2, ..., k, k+1\}$, primetimo da postoje dve mogućnosti:

• Svih $j$ izabranih utakmica su iz skupa $\{1, 2, ..., k\}$, tj. nije izabrana utakmica $k+1$,
• Jedna od izabranih utakmica je baš $k+1$. Onda je preostalih $j-1$ utakmica iz skupa $\{1, 2, ..., k\}$. Pri tome se svaki tiket sa $j-1$ utakmicom može proširiti do tiketa sa $j$ utakmica dodavanjem utakmice $k+1$. Zbog distributivnosti množenja u odnosu na sabiranje, zbir svih proizvoda sa $j$ izabranih utakmica, gde je poslednja baš utakmica $k+1$ biće jednak proizvodu kvote za tu utakmicu $k+1$ i zbira proizvoda svih tiketa sa $j-1$ utakmicom (gde su sve te utakmice iz skupa $\{1, 2, ..., k\}$ .

Na osnovu ovog razmatranja može se izvesti formula za izračunavanje zbirova: $None$ pr_{i,j}^{(k+1)}= $$\begin{cases} pr_{i,j}^{(k)} + pr_{i,j-1}^{(k)} \cdot q_{i,k+1}, &\text{ako je }j\leq k+1\ 0, &\text{ako je }j > k+1 \end{cases}$$ . $None$ U gornjem izrazu $q_{i,k+1}$ predstavlja kvotu za utakmicu $k+1$ u ligi $i$.

Kada imamo zbirove proizvoda sa fiskiranim brojem utakmica za svaku ligu, onda sličnim postupkom određujemo zbirove proizvoda kvota na tiketu koji sadrži utakmice iz raznih liga. Označimo sa $gpr_{k,j}$ zbir proizvoda svih tiketa koji imaju tačno $j$ utakmica iz prvih $k$ liga. Tada će važiti da je $None$ gpr_{1,j}^{(1)} = pr_{1,j}. $None$ Lako se zaključuje da ako iz prvih $k+1$ liga treba izbrati tačno $j$ utakmica, to možemo uraditi tako što iz lige broj $k+1$ izaberemo bilo koji dozvoljeni broj utakmica (ne veći od $j$) a ostatak dopunimo iz prvih $k$ liga. Mi već imamo izračunate zbirove proizvoda kvota za sve moguće brojeve utakmica na tiketu. Ako uvedemo oznake $None$ c_{i,j} = \begin{cases} 1,&\text{ može izabrati tačno $j$ utakmica iz lige $i$}\ 0,&\text{ ne može se izabrati tačno $j$ utakmica iz lige $i$} \end{cases}, $None$ onda se $gpr_{k+1,j}$ može računati na sledeći način $None$ g_{k+1,j} = \sum_{j'=1}^{\min(M,j)} c_{k+1,j'}\cdot pr_{k+1,j'}\cdot gpr_{k,j-j'} $None$ Nakon određivanja svih pomenutih zbirova proizvoda potrebno je samo odgovarajuće zbirove pomnožiti sa bonusima i sabrati: $None$ \sum_{j}^{N\cdot M} F_j \cdot gpr_{N,j} $None$ Ovde je sa $F_j$ označen bonus za tiket sa $j$ utakmica.

Napomenimo da se sve operacije izvode po modulu $10^9+7$, tj. svaki put posle izvedene operacije (sabiranje ili množenje) se određuje ostatak pri deljenju sa $10^9+7$.

Na kraju, par reči o složenosti postupka. Složenost računanja matrice $pr$ je $O(N\cdot M^2)$, a složenost računanja matrice $gpr$ je $O(N^2\cdot M^2)$.

Algoritamske smernice

Written with StackEdit.