Našou úlohou je nájsť lexikograficky najmenší možný reťazec s tým, že vieme niektoré písmenká duplikovať.

Bruteforce

Najpriamočiarejšie je vyskúšať všetky možné spôsoby duplikácie písmenok a vybrať z nich taký spôsob, ktorý tvorí lexikograficky najmenší reťazec. Tento bruteforce vieme napísať napríklad rekurzívne. Pre každý index $i$, ak môžeme, tak vyskúšame oba varianty — duplikáciu aj neduplikáciu. Udržiavame si popritom pomocný reťazec $C$ a postupnými rekurzívnymi volaniami sa dostaneme na index $n$, v ktorom lexikograficky porovnáme $C$ s doteraz lexikograficky najmenším videným reťazcom. Na koniec už len vypíšeme riešenie.

No existuje aj jednoduchší a rýchlejší spôsob, ako napísať rovnaký bruteforce. Využijeme na to bitmasky. Najprv si vytvorme pomocné pole $Q$. Nech $Q$ obsahuje všetky indexy $i$, na ktorých $T_i = 1$. Označme si veľkosť tohto poľa $m$. Čo spravíme je, že preiterujeme čísla $b \in 0 \dots 2^m - 1$. Teraz, každé číslo $b$ reprezentuje v binárnej sústave nejakú konfiguráciu — ak je $j$-ty bit v $b$ flipnutý, tak písmenko na indexe $Q_j$ duplikujeme, inak nie. Stačí už len vybrať riešenie s lexikograficky najmenším reťazcom a ho vypísať.

Obidve riešenia majú časovú zložitosť $O(n*2^m)$, pretože prechádzame všetky možné konfigurácie a pamäťovú zložitosť $O(n)$. Takéto riešenie nám vie dať štyri body.

Ak si chcete o podobných bruteforceoch niečo viac prečítať, tak určite odporúčam si prejsť tento text.

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define ff first
#define ss second

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    string S, T;
    cin >> N >> S >> T;

    vector<int> opts;
    for (int i = 0; i < N; i++)
        if (T[i] == '1')
            opts.push_back(i);

    int m = opts.size();
    string res = S;

    for (int bit = 0; bit < (1 << m); bit++)
    {
        int idx = 0;
        string cand = "";

        for (int i = 0; i < N; i++)
        {
            cand += S[i];
            if (idx < m && opts[idx] == i)
            {
                if (bit & (1 << idx))
                    cand += S[i];
                ++idx;
            }
        }

        if (cand < res)
            res = cand;
    }

    cout << res << endl;
}

Zaujímavá myšlienka

Skúsme sa zamyslieť, ako skonštruovať optimálne riešenie bez použitia hrubej sily. Uvažujme, že máme zatiaľ optimálne riešenie pre prvých $i$ písmen a práve sa rozhodujeme, či duplikovať písmenko na indexe $i$. V prvom rade, rozhodne vieme povedať, že každé jedno riešenie bude obsahovať písmeno $S_i$, potenciálne jeho duplikát a písmeno $S_{i+1}$, v uvedenom poradí. Zjavne, ak sa písmeno $S_{i+1}$ nachádza neskôr v abecede ako $S_i$, tak na zachovanie optimálnosti budeme musieť $S_i$ duplikovať. Ak by sme tak neurobili, tak riešenie nemôže byť optimálne, pretože pre riešenie, v ktorom písmeno neduplikujeme, vieme vždy duplikáciou $S_i$ "vložiť" lexikograficky menšie písmeno pred $S_{i+1}$, čím prefix po písmeno $S_{i+1}$ lexikograficky zmenšíme. Podobným postupom vieme tiež ukázať, že ak sa $S_{i+1}$ nachádza skôr v abecede ako $S_i$, tak sa neoplatí duplikovať písmeno $S_i$.

Čo ale s prípadom $S_i = S_{i+1}$? Postupujme podobne ako v predošlých prípadoch. Rozhodne vieme povedať, že každé jedno riešenie musí obsahovať písmeno $S_i$, potenciálne jeho duplikát, potom $S_{i+1}$, znovu potenciálne jeho duplikát, potom $S_{i+2}$, $\dots$, až po prvé také písmeno $S_j$, kde $S_j \neq S_i$ (ak by také písmeno neexistovalo, tak uvažujme, že $S_j$ je prázdny znak). Poďme si znova rozobrať, aké všetky prípady môžu nastať. Ak sa písmeno $S_j$ nachádza v abecede neskôr ako písmeno $S_i$, a taktiež prefix pre prvých $i$ písmen je optimálny, tak na zachovanie optimálnosti musíme z podobného argumentu ako predtým $S_i$ duplikovať. Naopak, ak $S_j < S_i$, tak $S_i$ duplikovať nebudeme, keďže duplikáciou by sme len oddialili písmeno $S_j$ väčším písmenom. No a prípad $S_i = S_j$ zo stanovenej podmienky nastať nemôže. Takto sme ukázali, že duplikovanie písmena sa oplatí práve vtedy, keď prvé iné písmeno, ktoré sa nachádza za ním, je v abecede neskôr.

Optimálne riešenie

Úloha sa nám teda redukovala na úlohu nájdenia prvého iného písmena. Konkrétnejšie, pre každý index $i$ chceme byť schopní nájsť taký index $j$, kde $i < j$, a tiež $S_i \neq S_j$. Triviálny spôsob, ako toto docieliť, je prosté iterovanie od indexu $i + 1$ až do bodu, dokým nenájdeme prvé iné písmeno. Takéto riešenie má časovú zložitosť $O(n^2)$ a môžete si rozmyslieť, že pomocou techniky dvoch bežcov vieme takéto riešenie zlepšiť na $O(n)$.

My si ale ukážeme jednoduchší spôsob, ako túto úlohu vyriešiť. My vieme tieto indexy $j$ predrátať. Vytvorme si pomocné pole $P$ veľkosti $n$. Nech $P_{n-1} := n$. Teraz, iterujme cez pole od konca. Pre index $i \in n-2 \dots 0$ skontrolujeme, či sa $S_i$ a $S_{i+1}$ rovnajú. Ak áno, tak prvé iné písmeno pre index $i$ je rovnaké ako pre index $i+1$, a teda $P_i := P_{i+1}$. Ak sa $S_i$ a $S_{i+1}$ nerovnajú, tak zjavne $P_i := i + 1$.

Riešenie pôvodnej úlohy teda vyzerá tak, že postupne budujeme optimálne riešenie. Ak $T_i = 1$, tak skontrolujeme písmeno na indexe $P_i$, a ak sa nachádza neskôr v abecede ako $S_i$, tak ho duplikujeme a do optimálneho riešenia pridáme dvakrát $S_i$. Inak pridáme $S_i$ len raz.

Riešenie má časovú aj pamäťovú zložitosť $O(n)$.

Python a string appendy

Mnohým z vás, ktorí ste riešili úlohu v Pythone, sa mohlo stať, že ste mali optimálne riešenie, no neprechádzalo vám na poslednú sadu. Dôvodov prečo môže byť veľa, no jedna obzvlášť zákerná vec, na ktorú si musíte dávať pozor sú string appendy v Pythone. Python, podobne ako mnoho iných programovacích jazykov, používa nemenné (immutable) stringy (reťazce). To znamená, že ak raz vytvoríme nejaký reťazec, tak jeho obsah sa už potom nedá zmeniť. Akákoľvek zmena alebo upravenie reťazca v skutočnosti funguje tak, že Python vytvorí úplne nový objekt reťazca a starý zostane v pamäti nezmenený.

Táto vlastnosť má mnohé výhody, no bohužiaľ prináša aj zopár škaredých nevýhod. Jednou z nich je, že spomínané string appendy fungujú trošku inak, než v jazykoch, kde sú stringy mutable. Kebyže v C++ appendujeme pomocou “+=”, táto operácia bude mať časovú zložitosť lineárnu od veľkosti reťazca, ktorý appendujeme. V Pythone, kde sú ale stringy immutable, operácia “+=” nepridáva do pôvodného reťazca reťazec, ktorý appendujeme, ale vytvorí kompletne nový string, do ktorého nakopíruje oba stringy. Následne určí adresu tohto nového stringu premennej, ktorá držala adresu stringu pred appendom. No a keď pomocou “+=” appendujeme vo for loope stringy, tak vďaka tomuto faktu časová zložitosť tohto for loopu môže byť až $O(n^2)$ (nemusí nastať vždy, Python má v sebe nakódované nejaké optimalizácie, napr. keď do stringu appendujeme len jedno písmeno, tak taký append by mal časovú zložitosť $O(1)$). Viac si o tomto môžete prečítať tu.

n = int(input())

s = input().strip()
bi = input().strip()

b = [c == '1' for c in bi]

closest = [''] * n
cur = s[n - 1]
closest[n - 1] = s[n - 1]

for i in range(n - 2, -1, -1):
    if s[i] == cur:
        closest[i] = closest[i + 1]
    else:
        closest[i] = cur
    cur = s[i]

out = []

for i in range(n - 1):
    out.append(s[i])

    if s[i] < closest[i] and b[i]:
        out.append(s[i])

out.append(s[n - 1])

print(''.join(out))

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define ff first
#define ss second

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    string S, T;
    cin >> N >> S >> T;

    vector<int> nxt(N, -1);
    for (int i = N - 2; i >= 0; i--)
    {
        if (S[i] != S[i + 1])
            nxt[i] = i + 1;
        else
            nxt[i] = nxt[i + 1];
    }

    string res = "";
    for (int i = 0; i < N; i++)
    {
        res += S[i];
        if (T[i] == '1' && nxt[i] != -1 && S[nxt[i]] > S[i])
            res += S[i];
    }

    cout << res << endl;
}