6. Výtvarný ateliér (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

Adam a Samo mali už odjakživa vzťah k výtvarnému umeniu, aj keď sa mu nevenujú profesionálne. Obaja išli na vysokú školu študovať nejakú odnož informatiky, no každý na inej univerzite a v inej krajine. Počas svojho štúdia sa aktívne podieľajú na príprave Korešpondenčnej Súťaže Papieroskladania. Keď sa ale naskytla ďalšia aktivita spojená s umením, neváhali a išli do toho.

V rámci medzinárodného a medziuniverzitného projektu výtvarného ateliéru Adam a Samo spolupracujú na vytváraní farebných ozdobných reťazí. Ide o reťaze, ktorých oká sú vyrobené z farebného papiera, pričom farieb je 26. Lenže, obaja už dokončili reťaze, keď zistili, že reťaze by mali byť vlastne rovnaké!

Adam je ale momentálne zahltený inými povinosťami, tak ostáva na Samovi, aby svoju reťaz patrične upravil.

Poraďte mu, ako má upraviť svoju reťaz!

Úloha

Máte dve reťaze - Adamovu a Samovu. Reťaz má daný začiatok a koniec (neviete ju teda otočiť). Je opísaná postupnosťou farieb ôk od jej začiatku po koniec. Samo má k dispozícii nožnice, fixky, a dokonca aj predpripravené kusiská reťazí, takže vie buď:

odstrihnúť súvislú časť reťaze a spojiť odstrihnuté miesta dokopy. Reťaz nemôže byť v procese obrátená!
- z abcd tak môže vzniknúť acd, bcd, bc ale nie adc alebo cda
vložiť nejaký súvislý kus reťaze medzi dve oká (alebo na koniec alebo začiatok reťaze)
- z abcd tak môže vzniknúť abbbcd, alebo aefgbcd, alebo kspabcd
prefarbiť oko na inú farbu
- z abcd tak môže vzniknúť abce

Tieto operácie vie Samo ľubovoľne kombinovať.

Chcel by ale, aby bol s výsledkom spokojný. Napríklad so svojou pôvodnou reťazou bol spokojný a je smutný, ak ju musí upravovať. Spokojnosť Samo kvantifikuje nasledovne:

Za každé nezmenené oko (neodstránené, ani neprefarbené) je o \(m\) bodov spokojnejší
Za každý súvislý odstránený úsek je o \(d\) bodov menej spokojný.
Za každý súvislý vložený úsek je \(i\) bodov menej spokojný.
Za každé prefarbenie oka je o \(r\) bodov menej spokojný.

Čísla \(i\) a \(r\) sú konštanty a nezávisia od dĺžky vloženého, respektíve odstráneného úseku.

Farieb existuje 26 a sú označené malými písmenami anglickej abecedy. Zistite, ako najviac spokojný môže Samo zostať, a nejaký spôsob, ako môže svoju reťaz upraviť.

Formát vstupu

V prvom riadku vstupu sa nachádzajú štyri čísla:

číslo, o koľko bude spokojnejší za každé nezmenené oko, \(m\)
cena odstránenia súvislej časti ôk \(d\),
cena vloženia súvislej reťaze ôk \(i\)
cena prefarbenia oka \(r\).

Nasledujú dva riadky. V prvom z nich sa nachádza popis Samovej reťaze a na druhom popis Adamovej reťaze. Oba popisy sú reťazec z malých písmen anglickej abecedy.

Platí, že reťaze nepresahujú dĺžku \(5\,000\) a \(0 \leq m, d, i, r \leq 100\,000\).

Formát výstupu

Vypíšte jeden riadok: najväčšiu spokojnosť, ku ktorej sa vie Samo dopracovať.

Hodnotenie

Úloha má štyri sady. Maximálne dĺžky reťazí v nich budú postupne \(500\), \(2\,000\), \(2\,000\) a \(5\,000\).

V druhej sade, navyše platí, \(d = i = r = 0\), teda Samo nestráca žiadnu spokojnosť.

Príklady

Input:

1 2 2 1
abccb
accba

Output:

Samo by mal vymazať prvé oko s farbou ‘b’ zo svojej reťaze, a pridať oko s farbou ‘a’ na koniec. Takto sa štyroch svojich ôk nedotkne (+4 body spokojnosti), a raz odstráni ‘b’ (-2 body) a raz pridá ‘a’ (-2 body). Všimnite si, že napriek tomu, že je prefarbenie lacnejšie, než vymazanie, neoplatí sa mu.

Input:

3 2 2 1
asdffflp
kpfffor

Output:

Samo by mal vymazať ‘asd’ zo začiatku svojej reťaze a pridať tam ‘kp’. Na druhej strane, mal by ‘lp’ zmeniť po jednom na ‘or’. Takto bude \(-2-2+3+3+3-1-1 = 3\) bodov spokojný

Input:

1 1 1 10
kms
ksp

Output:

Samo nechce prefarbovať. Najlepšie mu je teda vystrihnúť preč \(m\) a pridanie \(p\)

Input:

10 1 1000 100
kspoooksp
kspkspksp

Output:

-240

Samo tu potrebuje zmeniť ‘ooo’ na ‘ksp’. Pridávanie mu výrazne uberá na spokojnosti, tak radšej ich po jednom prefarbí.

Ako si mohol skúsenejší riešiteľ isto všimnúť, úloha sa rieši dynamickým programovaním.

Zjednodušene, spočítame si hodnotu výsledku pre menšie časti zadania a skombinujeme aby sme dostali výsledok.

Pomalé riešenie

Predstavme si, že by sme pre pozície \(l\), \(j\) vedeli nasledovné:

Koľko najviac spokojnosti vieme dostať, ak by sme mali len prvých \(l\) ôk zo Samovej reťaze, a len prvých \(j\) ôk z Adamovej reťaze a:

Samo vymazal nejaký neprádzny koncový úsek svojich ôk. Označme toto číslo ako \(D[l][j]\)
Samo na koniec svojej reťaze pridal nejaký neprázdny úsek ôk. Označme toto číslo ako \(I[l][j]\)
Samo buď posledné oko nezmenil (ak sú koncové¹ oká rovnaké), alebo prefarbil (ak sú rôzne). Označme toto číslo ako \(M[l][j]\)

Navyše, označme si najväčšiu spokojnosť akú vie Samo dostať pre takéto začiatky reťazí ako \(S[l][j]\).

Všimnime si, že \(S[l][j] = \max(D[l][j], I[l][j], M[l][j])\)

Predstavme si, že máme spočítanú hodnotu \(S\) pre všetky skoršie začiatky (vrátane \(S[l][j-1]\) a \(S[l - 1][j]\)). Ako z toho získať hodnotu \(S[l][j]\)?

Keďže \(S[l][j]\) je minimum z \(D[l][j], I[l][j]\) a \(M[l][j]\), chceme spočítať tie.

Všimnime si, že

\[ M[l][j] = \begin{cases} S[l-1][j-1] + m & \text{ak sú } i \text{-te Samovo oko a } j \text{-te Adamovo oko rovnakej farby} \\ S[l-1][j-1] - r & \text{ak sú rôznej farby} \\ \end{cases} \]

Pre \(I\) a \(D\) vieme vyskúšať všetky možné dĺžky pridaného, resp. odstráneného úseku, teda \(I[l][j]\) je maximum z \(S[l][j-k] - i\), pre všetky \(1 \leq k \leq j\). A nápodobne pre \(D[i][j]\).

Takto vieme postupne prejsť všetky začiatky a napokon nájsť aj riešenie pre celé reťazce v čase \(O(|S||A|(|A| + |S|))\), kde \(|S|\), \(|A|\) sú postupne dĺžky Samovho a Adamovho reťazca, a v pamäti \(O(|S||A|)\).

#include<bits/stdc++.h>
#define ii pair<int, int>
#define FOR(i,n)	for(int i=0;i<(int)n;i++)

using namespace std;

const int inff = 1000000999;

int compute_score(int ma, int d, int ins, int r, string S, string A) {
    int n = S.size();
    int m = A.size();
    
    vector<vector<int> > V_gap(n + 1, vector<int>(m + 1, -inff)),
                            F(n + 1, vector<int>(m + 1, -inff)),
                            E(n + 1, vector<int>(m + 1, -inff));
    
    V_gap[0][0] = 0;
    
    FOR(i, n + 1) {
        F[i][0] = -d;
        V_gap[i][0] = max(V_gap[i][0], -d);
    }
    
    FOR(j, m + 1) {
        E[0][j] = -ins;
        V_gap[0][j] = max(V_gap[0][j], -ins);
    }
    
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            FOR(k, j) {
                E[i][j] = max(V_gap[i][k] - ins, E[i][j]);
            }
            FOR(k, i) F[i][j] = max(F[i][j], V_gap[k][j] - d);
            V_gap[i][j] = max(max(F[i][j], E[i][j]), 
                              V_gap[i - 1][j - 1] + (S[i - 1] == A[j - 1] ? ma : -r));
        }
    }
    return V_gap[n][m];
}

int main() {
    int m, d, ins, r;
    cin >> m >> d >> ins >> r;
    string samo, adam;
    cin >> samo >> adam;
    cout << compute_score(m, d, ins, r, samo, adam) << endl;
}

Ako rýchlejšie?

Chceli by sme zrýchliť naše riešenie. Čo robíme navyše?

Predstavme si, že okrem hodnôt \(S\) si pamätáme aj hodnoty \(I\), \(D\) pre predchádzajúce začiatky. Potom si všimnime, že akonáhle je Samovi lepšie vložiť väčší úsek ako \(1\), potom \(I[l][j] = I[l][j-1]\). Inak je ideálne vložiť jediné oko, teda \(I[l][j] = \max(I[l][j-1], S[l][j-1] - i)\). Nápodobný vzorec získame pre hodnoty \(D\).

Takto nám stačí pre výpočet \(S[l][j]\) spraviť konštantne veľa operácií, takže dostávame časovú zložitosť \(O(|S||A|)\) s rovnakou pamäťovou zložitosťou ako predtým.

Ako to ešte zlepšiť?

Čas už nezlepšíme, ale máme tu ešte pamäť. Všimnime si, že pri počítaní \(S[l][j]\) sa pozeráme len na hodnoty s indexami najmenej \([l-1][j-1]\). Teda nám stačí si pamätať posledný riadok a stĺpec výpočtu, teda iba lineárne veľa údajov.

Takže dostávame pamäťovú zložitosť \(O(|S| + |A|)\).

#include<bits/stdc++.h>

using namespace std;

const int inff = 1000000999;

int compute_score(int me, int d, int ins, int r,
                            string U, string V) {
    int n = U.size();
    int m = V.size();
    
    vector<int> V_gap(m + 1, 0), F(m + 1, -inff);
    
    for (int j = 1; j <= m; j ++) {
        V_gap[j] = -ins;
    }
    
    for (int i = 1; i <= n; i ++) {
        vector<int> new_V_gap(m + 1), new_F(m + 1);
        new_V_gap[0] = -d;
        new_F[0] = -d;
        int E = -inff;
        
        for (int j = 1; j <= m; j ++) {
            int G = (V_gap[j - 1] +
                           (U[i - 1] == V[j - 1] ? me : -r));
            E = max(E, new_V_gap[j - 1] - ins);
            new_F[j] = max(F[j], V_gap[j] - d);
            new_V_gap[j] = max(G, max(E, new_F[j]));
        }
        
        F = new_F;
        V_gap = new_V_gap;
    }
    
    return V_gap[m];
}

int main() {
    int me, d, ins, r;
    cin >> me >> d >> ins >> r;
    string samo, adam;
    cin >> samo >> adam;
    cout << compute_score(me, d, ins, r, samo, adam) << endl;
}

Máme to naozaj vyriešené?

A naozaj, v riešení hore sme sa nezmienili čo robiť so \(S[l][j]\), keď je jedno z indexov \(0\). Schválne, čo jediné môže Samo spraviť ak má on alebo Adam prázdny string?

koncové v tomto prípade znamená \(l\)-te Samovo a \(j\)-te Adamovo oko↩︎

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.

6. Výtvarný ateliér vzorové riešenie

Zadanie

Úloha

Formát vstupu

Formát výstupu

Hodnotenie

Príklady

Pomalé riešenie

Ako rýchlejšie?

Ako to ešte zlepšiť?

Máme to naozaj vyriešené?

Diskusia