Гуштер
Аутор: Андреј Ивашковић
Текст и тест примери: Андреј Ивашковић
Тестирање: Алекса Милисављевић
Анализа решења: Андреј Ивашковић
Овај задатак се решава динамичким програмирањем, што се види по томе што је реч о оптимизацији и по томе што наћи оптимално решење за дати улаз зависи од оптималних решења за подниске тог улаза.
Основа решења за три подзадатка је иста: добити 50 или 100 поена на овом задатку захтева да се примете. Нека је n дужина дате ниске s (индексиране од нуле).
Решење за n \leq 100
Дефинишимо дводимензиони низ \mathit{dp} формата (n+1)\times(n+1):
-
\mathit{dp}[i][j] за i,j>0: оптималан змија-скор који суфикс ниске s дужине i може да оствари, уколико се у првог реду логотипа налази j знакова; ако не постоји ниједан такав дозвољен логотип, -\infty;
-
\mathit{dp}[i][0] и \mathit{dp}[0][j] могу да се игноришу и немају никакво посебно значење.
Уколико знамо све вредности \mathit{dp}[i][j], тада је решење једнако \max_{2 \leq j \leq n} \{\mathit{dp}[n][j]\}: оптимално решење садржи било који (дозвољен) број симбола у првом реду.
Најпре приметимо неке основне чињенице о \mathit{dp}[i][j] које служе као темељ одређивања коначног решења:
-
\mathit{dp}[i][i] = 0, реч је о решењу у ком цео логотип за суфикс дужине i стаје у један ред;
-
\mathit{dp}[i][j] = -\infty за i<j;
-
\mathit{dp}[i][1] = -\infty (није могуће да у било ком реду буде само један знак).
За даље рачунање се ослањамо на наредно запажање:
Ако суфикс ниске s дужине i садржи j знакова (1<j<i), оптималан змија-скор који може да се оствари је највећи од свих збирова \mathit{dp}[i-j][k] и броја поклапања знакова уколико се у првом реду налази j, а у другом i знакова.
Број поклапања може да се израчуна провером да ли се поклапају знаци s на позицијама n-i+j+p-1 и n-i+j-p, при чему се p мења. Ако дефинишемо P(t,p) као индикатор да ли се ови знаци на позицијама n-t+p-1 и n-t-p поклапају (дакле 0 или 1; 0 је одговор и у случају да је један од ових знакова ван опсега ниске), претходна чињеница може да се запише у виду наредне рекурентне везе:
\mathit{dp}[i][j] = \max_{2<k\leq i-j} \{\mathit{dp}[i-j][k] + \sum_{p=1}^{\min(j,k)} P(i-j,p)\}
Све вредности \mathit{dp}[i][j] могу да се одреде пратећи ову формулу.
У псеудокоду, овако изгледа главни део алгоритма:
for i in 1 .. n:
for j in 2 .. i:
dp[i][j] = -∞
for k in 2 .. j:
broj_poklapanja = 0
for p in 1 .. min(j, k):
broj_poklapanja += P(i - j, p)
dp[i][j] = max(dp[i][j], dp[i - j][k] + broj_poklapanja)
Коначна временска сложеност је O(n^4), а меморијска O(n^2).
Решење за n \leq 500
У овом случају потребно је приметити да при одређивању \mathit{dp}[i][j] и \mathit{dp}[i][j+1] треба да водимо рачуна о наредне две суме:
-
\sum_{p=1}^{\min(j,k)} P(i-j,p);
-
\sum_{p=1}^{\min(j,k+1)} P(i-j,p)
а њихова разлика је или 0 или последњи сабирак у збиру: P(i-j,k+1).
Претходно решење стога може да се упрости тиме што се променљива broj_poklapanja ажурира сваки пут када се ажурира k. Имплементација се мења на следећи начин:
for i in 1 .. n:
for j in 2 .. i:
dp[i][j] = -∞
broj_poklapanja = P(i - j, 1)
for k in 2 .. j:
if k <= j:
broj_poklapanja += P(i - j, k)
dp[i][j] = max(dp[i][j], dp[i - j][k] + broj_poklapanja)
Резултујућа сложеност је O(n^3), а меморијска O(n^2).
Главно решење
Решење за свих 100 поена ради у временској сложености O(n^2) и заснива се на избегавању понављања непотребног рада.
Приметимо да у решењу претходног подзадатка имамо итерације по j и по k, које одређују дужине два узастопна реда.
Како се ажурира j, мења се последњи знак у првом реду и први знак у другом реду, као и подаци о свим поклапањима.
Стога у оптимизованом решењу желимо да искористимо исте податке о поклапањима што је могуће дуже тако што ће спољна итерација бити по положају последњег знака првог реда.
Суфиксу дужине z+d, у ком први ред има дужину d, први ред се завршава знаком са индексом n-z-1 и други ред почиње знаком са индексом n-z – спољна итерација је по z, унутрашња по d.
За добијање коначног решења неопходно је посматрати шта се дешава у случају два суседна реда у логотипу уколико други ред починје знаком са индексом n-z. Претпоставимо да први ред има дужину d.
- Ако је први ред краћи од другог, број знакова који се поклапају је једнак \sum_{p=1}^{d} P(i-j,p).
Дакле, једино је питање одредити неко k \geq d тако да је \mathit{dp}[z][k] максимизовано.
- Ако је први ред дужи од или једнаке дужине као и други, тада нас међу свим \mathit{dp}[z][k]+\sum_{p=1}^{k} P(i-j,p) за које је k\leq d занима оно највеће.
У првом случају је довољно увести матрицу m дефинисану на следећи начин:
-
m[i][j] = \max_{j\leq k\leq i}\{\mathit{dp}[i][k]\} за j \leq i
која може да се израчуна помоћу рекурентне везе:
-
m[i][i] = \mathit{dp}[i][i] = 0;
-
m[i][j] = \max\{\mathit{dp}[i][j],m[i][j+1]\}, за 0\leq j<i.
У другом случају радимо сличну ствар као у другом подзадатку: пратимо актуелно највеће \mathit{dp}[z][k] + \sum_{p=1}^{k} P(i-j,p) за све k\leq d.
То води наредном псеудокоду (изузев иницијализације):
for d in 2 .. n:
broj_poklapanja[1] = P(i - j, 1)
sufiks_max[d][d] = dp[d][d]
poklapanje_plus_ostatak[0] = 0;
for k in 1 .. d:
sufiks_max[d][d - k] = max(sufiks_max[d][d - k + 1], dp[d][d - k]);
poklapanje_plus_ostatak[k] = 0;
for t in 2 .. min(d, n - d):
broj_poklapanja[t] = broj_poklapanja[t - 1] + P(d, t);
poklapanje_plus_ostatak[t] = broj_poklapanja[t] + dp[d][t];
dp[d + t][t] = max(dp[d + t][t], sufiks_max[d][t] + broj_poklapanja[t]);
max_zbir = 0;
for j in 2 .. (n - d):
if j <= d:
max_do_sad = max(max_do_sad, poklapanje_plus_ostatak[j]);
dp[d + j][j] = max(dp[d + j][j], max_do_sad);
За крај, поменимо да је могуће добити све поене чак и када се имплементира решење сложености O(n^2 \log n), под условом да је константа сакривена O-нотацијом довољно мала.
Једно овакво решење се заснива на идејама из прва два подзадатка, при чему се рачунање траженог минимума врши коришћењем сегментног стабла.
Међутим, решење временске сложености O(n^2) је краће и брже.