8. Yucatán na polia! vzorové riešenie

2
5
1 1 3 3 1
3
1 2 3

13 2
3 4
1 5
3 3
1 1
2 2
3 3

Skúšame všetky možnosti

Možnosť ktorú (skoro) vždy ide skúsiť, je vyskúšať všetky možnosti. Všimnime si, že pre pole s \(n\) políčkami, po každom zožatí existuje \(2^n\) možností ako pole práve vyzerá – každé políčko môže byť celé zožaté alebo celé nezožaté. Keďže každé žatie by malo zožať aspoň jedno políčko, počet nezožatých políčok sa nám postupne zmenšuje.

Na tejto myšlienke vieme podstaviť riešenie pomocou bitmaskovej dynamiky. Ak ste o tomto princípe ešte nepočuli, jedná sa v princípe o reprezentovanie stavov – polí boolov, ako celé čísla. V našom prípade bity s hodnotou \(1\) reprezentujú políčka, ktoré sú ešte nezožaté. Takže stavy sú reprezentované celými číslami od 0 po \(2^n-1\).

Taktiež si všimnime, že ak \(a < b\) sú možné stavy, potom sa nikde nevieme dostať z \(a\) po \(b\) – žatím sa reprezentácia poľa nikdy nezvýši.

Na tomto princípe teraz postavíme dynamiku: postupne si prejdeme všetky stavy a pre každý zrátame, koľko šťastia vieme bohom zabezpečiť od dosiahnutia tohto stavu až po zožatie celého poľa. Stavy prejdeme v poradí od \(0\) po \(2^n-1\). Toto nám zaručí, že keď spracúvame nejaký stav, všetky stavy z neho dosiahnuteľné už budú spracované. Pre každý stav si pozrieme všetky možnosti ktoré vieme zožať. Naoko ich je až \(O(n^2)\), avšak môžete si všimnúť, že sa vždy oplatí žať maximálny úsek kukurice - teda taký úsek, ktorý nevieme rozšíriť na žiadnu stranu, tak aby sme zožali viac (rovnakého) kusu kukurice.

Oplatí sa iba maximálny úsek

Toto tvrdenie si vieme zdôvodniť nasledovne. Bez ujmy na všeobecnosti sa môžeme tváriť, že žiadne už zožaté políčka ešte neexistujú. Predstavte si, že na začiatku zožneme úsek kukurice dlhý \(a\), hoci by sme ho mohli rozšíriť (bez ujmy na všeobecnosti doprava) o ďalšie políčko (povedzme na pozícii \(i\)). Bez ujmy na všeobecnosti sa všetky žatia môžu začínať aj končiť nezožatým políčkom.Takto sa teda žiadna žatva pred zožatím \(i\)-teho políčka nemôže spoliehať na to, že \(a\) políčok priamo naľavo od \(i\)-teho (pôvodne s rovnakou odrodou ako \(i\)-te) je už zožatých. Teda vieme ich žatvu posunúť, a zožať ich spolu s \(i\)-tym políčkom. Keďže \((a + b)^2 > a^2 + b^2\) pre \(a, b > 0\) takáto zmena vždy zvýši šťastie.

Ozbrojení s týmto pozorovaním, si teda môžme všimnúť, že existuje \(O(n)\) možných úsekov ktoré sa oplatí skúsiť: prejdeme si pole a tak ho rozdelíme na súvislé úseky, tak že každý úsek obsahuje len jeden typ kukurice, a každé dva vedľajšie úseky majú rôzne typy kukurice. Keďže každé políčko je v najviac jednom úseku, úsekov bude najviac \(n\), a žiadny z nich sa nedá rozšíriť o viac nezožatých políčok kukurice. Takže nám pre každý možný stav poľa stačí skúsiť najviac \(n\) možností na ďalšiu žatvu. Toto nám teda dá riešenie s časovou zložitosťou \(O(n 2^n)\), a s pamäťovou zložitosťou O(\(2^n)\) ktoré stačí na \(2\) body.

Na záver si všimnime, že na zrekonštruovanie riešenia, si nám stačí pamätať pre každý stav aký ďalší úsek máme zožať, takže toto nám nezničí pamäťovú zložitosť. Riešenie vieme z toho zrekonštruovať v lineárnom čase.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, n) for (int i = 0; i < (int)n; i++)
#define ii pair<int, int>
#define MP make_pair
#define SIZE(x) int(x.size())

ii next(int a, int i, vector<ii>& starts) {
    if (!(a & (1 << i)))
        return {a, 0};
    int j = i;
    int total = 0;
    int b = a;
    while (j < starts.size() - 1 && (starts[j].second == starts[i].second || (!(a & (1 << j))))) {
        if (a & (1 << j)) {
            total += starts[j + 1].first - starts[j].first;
            b ^= (1 << j);
        }
        j++;
    }
    return {b, total};
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> pole;
        vector<ii> starts;
        FOR(i, n) {
            int a;
            cin >> a;
            pole.push_back(a);
            if (i) {
                if (pole[i] != pole[i - 1]) {
                    starts.push_back({i, pole[i]});
                }
            } else {
                starts.push_back({i, pole[i]});
            }
        }

        int m = starts.size();
        starts.push_back({n, -1});

        vector<ii> dp(1 << m, {0, -1});

        FOR(a, 1 << m) {
            if (!a)
                continue;
            FOR(i, m) {
                if (a & (1 << i)) {
                    ii prel = next(a, i, starts);
                    dp[a] = max(dp[a], MP(dp[prel.first].first + prel.second * prel.second, i));
                }
            }
        }

        vector<ii> instructions;
        int a = (1 << m) - 1;
        while (a) {
            int zac = dp[a].second;
            int end = zac;
            while (end < SIZE(starts) &&
                   (starts[zac].second == starts[end].second || (!(a & (1 << end))))) {
                if (a & (1 << end))
                    a ^= (1 << end);
                end++;
            }
            instructions.push_back({starts[zac].first + 1, (end < m ? starts[end].first : n)});
        }

        cout << dp[(1 << m) - 1].first << " " << SIZE(instructions) << "\n";

        for (ii a : instructions) {
            cout << a.first << " " << a.second << "\n";
        }
    }
}

(Skoro) vzorák

Poďme sa zamyslieť nad nejakým polynomiálnym riešením. Ako pri hrubej sile, aj teraz sa bude jednať o dynamické programovanie. Problém na ktorý narazíme, ak sa pokúsime priamočiaro zlepšiť riešenie hrubou silou, je že ak zožneme nejaký úsek kukurice, riešenie sa nám nerozpadne na viacero nezávislých podproblémov - aj keď sú kusy poľa rozdelené už zožatým úsekom, vieme stále žať cez tento prázdny úsek. A pretože za jedno žatie získame štvorec šťastia, treba na to ísť múdrejšie. Totiž kontribúcie z oboch strán sú kombinované netriviálnym spôsobom – teda ak získame \(a\) z jednej, a \(b\) z druhej strany prázdneho úseku v jednom žatí, šťastie z toho žatia je \((a+b)^2 = a^2+b^2 + 2ab\).

Pozrime sa na prvé políčko kukurice. Keďže chceme dožať celé pole, niekedy v optimálnom riešení zožneme prvé políčko. Buď s ním nezožneme žiadne ďalšie políčko, alebo povedzme že v tom žatí zožneme na prvý raz aj nejaké ďalšie políčka. Povedzme že \(i\)-te je najľavejšie z nich. V tom prípade musíme pred týmto žatím zožať všetky políčka na pozíciach \(2,\dots,i-1\) (ak \(i\) je druhé políčko, potom netreba predtým zožať nič). Navyše tento interval políčok musíme zožať iba žatiami vnútri intervalu (inak by sme zožali políčko \(1\) alebo \(i\) skôr ako chceme).

Takto nám teda vlastne vznikne nezávislý podproblém: Daný je interval \([z, k]\), aké najväčšie šťastie vieme dosiahnuť ak žneme len kukurice na tomto intervale?

Avšak, toto nie je jediný problém, ktorý nám ostane. Zostane nám ešte otázka, ako maximalizovať šťastie z intervalu \([i, n]\), ak vieme že nám naľavo “odstáva” jedno nezožaté políčko kukurice rovnakého typu ako na políčku \(i\) (keďže najskôr zožneme interval \([2, i - 1]\), nezáleží nám kde presne sa to “odstávajúce políčko” nachádza (stačí nám vedieť že je naľavo od začiatku úseku).

Tak by sa mohlo zdať, že nám stačí vedieť vyriešiť dva podproblémy:

• Pre daný podinterval poľa, aké najväčšie šťastie vedia dosiahnuť žatím len na tomto úseku?
• Pre daný podinterval poľa, aké najväčšie šťastie vedia dosiahnuť žatím len tohto úseku ak je naľavo priamo dosiahnuteľné políčko s rovnakým typom kukurice ako najľavejšie políčko v úseku?

Avšak keď skúsime rekurzívne riešiť druhý problém, zistíme že sa nám kumulujú kukurice rovnakého typu: povedzme že riešime podproblém s úsekom \([z, k]\) a jednou “odstrávajúcou” kukuricou. Potom ak chceme najskôr zožať úsek \([z +1, i]\), tak nám v zostávajúcom úseku \([i+1,k]\) zústávajú \(2\) odstávajúce nezožaté kukurice naľavo! Chceme teda vyriešiť trochu viac všeobecný podproblém:

• Pre daný podinterval poľa, aké najväčšie šťastie vedia dosiahnuť žatím len tohto úseku ak je naľavo priamo dosiahnuteľných \(s\) políčok s rovnakým typom kukurice ako najľavejšie políčko v úseku?

Môžeme si všimnúť, že ak \(s=0\), potom toto zodpovedá prvému podproblému. Takže podproblém ktorý riešime je nasledovný:

Pre daný interval [z, k] a číslo \(s\geq 0\), aké najväčšie šťastie vedia Mayovia dosiahnuť zožatím intervalu \([z, k]\) ak majú navyše \(s\) kukuríc rovnakého typu ako kukurica na políčku \(z\) dostupných na zožatie naľavo od úseku.

Nazvime riešenie tohto problému \(dp[z][k][s]\). Potom si všimnime, že ak vieme riešenie pre všetky menšie intervaly, vieme spočítať túto hodnotu ako maximum z:

• \(dp[z + 1][k][0] + (s+1)^2\) – toto je prípad, že keď zožneme interval s \(z\)-tým políčkom, práve \(z\) bude posledné zožaté políčko
• Pre každé políčko \(i\) pre ktoré platí \(z < i \leq k\) a na ktorom rastie rovnaká odroda kukurice ako na políčku \(z\), \(dp[z + 1][i-1][0] + dp[i][k][s+1]\)

Samozrejme, pre prázdne intervaly, teda kde \(z = k\), riešenie je \(s^2\) (zožneme zostávajúce políčka). Všimnite si, že všetky zaujímavé hodnoty \(s\) sú medzi \(0\) a \(n\). Takto teda dostaneme teda dynamické programovanie s \(O(n^3)\) stavmi - to bude pamäťová zložitosť, a keďže potrebujeme \(O(n)\) operácií na spočítanie jednej hodnoty, časová zložitosť riešenia je \(O(n^4)\).

Aj na konštantách záleží: nerobme prácu navyše

A toto je optimálna časová zložitosť - lenže len asymptoticky. Čo to znamená? Väčšinou, keď riešime časové zložitosti sa nám všetky konštanty skryjú pod \(O\) – teda či program spraví \(100n^4\) alebo \(n^4 / 10\) operácií, stále má časovú zložitosť \(O(n^4)\). Lenže v druhom prípade bude bežať o dosť rýchlejšie, a pre vstupy na hranici časového limitu nám na tom bude veru záležať.

\(O(n^4)\) dynamika ktorú sme opísali hore má dosť zlú konštantu: ráta veľa vecí ktoré nemusí. Pri riešení hrubou silou sme si uvedomili, že ak vieme žací interval rozšíriť (o ďalšie políčka rovnakého kukuričného typu), vždy sa to oplatí. Takže napríklad, kedykoľvek keď máme viac kukuríc rovnakého typu za sebou v poli, vieme, že ich vždy budeme kosiť spolu. Takouto myšlienkou vieme spraviť prvú optimalizáciu riešenia: skomprimujme si pole tak, že si budeme pamätať dĺžku úsekov s rovnakou kukuricou a o aký typ sa jedná.

Napríklad z poľa \(1,1,3,3,1\) by nám vzniklo pole \((1, 2), (3,2), (1,1)\). Na takomto skomprimovanom poli vieme robiť dynamiku ako hore, len namiesto pripočítania jedného políčka, budeme pripočítať dĺžku úseku na ktorom sme. Takáto úprava síce v najhoršom prípade¹ riešenie nezlepší, ale na väčšine vstupov takáto základná optimalizácia zlepší čas behu niekoľkonásobne.

Na ďalšie pozorovanie si najskôr upravme notáciu. Pre \(i\)-ty typ kukurice majme \(c_i\) – počet políčok na ktorých sa pestuje. Všimnime si, že teda existuje najviac \(c_i\) možných začiatkov úsekov s touto farbou. Ak by \(j\)-te políčko typu \(i\) bolo aj začiatok úseku, potom sa oplatí uvažovať iba možné \(s\) (počet odstávajúcich nezožatých naľavo od úseku) medzi \(0\) a \(j-1\). Taktiež existuje nanajvýš \(c_i - j + 1\) možných úsekov ktorými sa oplatí zaoberať. Keďže \(j\)-te políčko s odrodou \(i\) musí byť na aspoň \(j\)-tej pozícii v poli ako takom², takže počet možných koncov úsekov je najviac \(n - j + 2\). V najhorošom prípade (keďže robíme horný odhad), je každé políčko tejto farby začiatok úseku, teda dostaneme, že v dynamike potrebujeme urobiť najviac

\[ \sum_i^n \sum_{j=1}^{c_i} j(c_i-j + 1)(n - j + 2) \leq \sum_i^n \frac{n(c_i+2)^3}{6} \]

iterácií³ (na spočítanie konečného výsledku – tým myslíme počet iterácií, ktoré naše forcykly v dynamike musia vykonať, resp. v rekurzívnej implementácii koľko volaní musíme spraviť). Všimnime si, dokopy je súčet všetkých \(c_i\) rovný \(n\). Akonáhle neexistuje typ kukurice pestovaný na nadpolovičnej väčšine políčok, vieme si ukázať, že v tejto situácii je suma maximalizovaná ak máme len dve odrody kukurice, a každá zaberá polovicu políčok. Vtedy dostaneme horný odhad približne \(n^4 / 24\).

Čo ak je nejakej odrody priveľa? Bez ujmy na všeobecnosti nech je kukurice typu \(1\) najviac. Vtedy si všimnite, že akonáhle \(c_1 > n/2\) (nejaký typ kukurice pestujeme na nadpolovičnej väčšine políčok), potom spravíme operácií vlastne o dosť menej. Keďže úseky rovnakého typu kukurice musia byť oddelené iným typom kukurice, tak celkovo úsekov nebude dokopy viac ako \(2(n - c_1) + 1\). Teda tento najväčší typ kukurice nemôže zaberať viac ako \(n - c_1 + 1\) úsekov. Spravme si druhý horný odhad práce, ktorú musíme v tomto prípade urobiť. Existuje najviac \(2(n-c_1) + 1\) možných koncov (keďže sa neoplatí počítať dynamiku pre konce, ktoré nie sú konce úsekov). Teda, keby bolo \(j\)-te políčko s kukuricou typu \(i\) začiatkom úseku, na spočítanie dynamík s týmto začiatkom by sme potrebovali najviac \(j(c_1-j + 1)\cdot (2(n-c_1) + 1)\) iterácií (tu sme zrecyklovali predchádzajúci argument). Všimnime si, že toto číslo je maximalizované pre \(j = (c_1 + 1) / 2\). Keďže nebudeme mať viac ako \(n-c_1+1\) začiatkov ktoré nás zaujímajú, dostaneme že pre túto odrodu budeme musieť spraviť najviac

\[ \frac{(n - c_1 + 1)(2(n-c_1) + 1)(c_i+1)^2}{4} \approx \frac{(n - c_1)^2 c_i^2}{2} \]

A teda celkovo, berúc do úvahy aj ostatné kukurice, pomocou prvého odhadu dostaneme, že nespravíme viac ako približne \(n(n-c_1)^3/6+ (n-c_1)^2 c_1^2 / 2\) iterácií. Môžeme si všimnúť⁴, že na intervale \([n/2, n]\) táto funkcia klesá, a teda vieme počet iterácií zas odhadnúť pomocou \(c_i = n / 2\). Vyjde nám tak, že nám stačí približne \(n^4(1/48+1/32) = 5n^4/96 \leq n^4/19\), čo je len o niečo horšie ako predchádzajúci odhad⁵

Pre porovnanie, pre maximálne \(n\) v tejto úlohe, tento odhad vyjde na niečo pod \(10^8\) čo je zhruba na hrane toho, čo testovať ešte zvládne. Ak vám riešenie stále neprechádza, treba sa zamyslieť nad ďalšími faktormi – akú dátovú štruktúru používate na dynamiku? Robíte dynamiku alebo rekurziu s memoizáciou (hoci tá druhá naozaj navštívi len relevantné stavy, je v praxi pomalšia).

Rekonštrukcia riešenia

Vo vzoráku som zatiaľ nespomenula ako rekonštruovať riešenia. Je to hlavne záležitosť správnej implementácie. Ako zvyčajne, keď potrebujeme v dynamike rekonštruovať riešenie (nielen výsledok) pamätáme si pre každý stav nielen maximálne hodnoty šťastia, ale aj ako sme ho vedeli získať. Následne riešenie rekonštruujeme pomocou zásobníka, v čase lineárnom od veľkosti poľa (maximálny počet žatí). Postupujeme od konca, a treba si dobre rozmyslieť v akom poradí dávame žatia do stacku: pamätajme si že ak chceme prvé políčko úseku spojiť s nejakým ktoré nie je tesne napravo, musíme najskôr vyžať úsek medzi nimi.

Poznámka na záver - \(O(n^5)\) riešenie

Existujú aj iné dynamiky v polynomiálnom čase. Napríklad existuje \(O(n^5)\) riešenie ktoré stačí na \(4\) body, ale je (podľa autorkinho názoru) o niečo komplikovanejšie než vzorák. Ak sa chcete zamyslieť, uvažujte dynamické programovanie so stavmi: začiatok úseku, koniec úseku, a typ kukurice \(t\), ktorý chceme dosiahnuť na konci, a množstvo \(x\) koľko jej chceme dosiahnuť. Výsledok pre stav je maximálne šťastie, ktoré vieme dosiahnuť nejakým žatím po ktorom ostane na danom úseku \(x\) políčok s kukuricou typu \(t\). Všimnite si, že síce má toto riešenie stavov len \(O(n^3)\), rovnako ako \(O(n^4)\) riešenie, avšak, z každého stavu máme až \(O(n^2)\) možností kam sa pohnúť ďalej.

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, n) for (int i = 0; i < (int)n; i++)
#define ii pair<int, int>

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        /* kedze sa nam vzdy uplati zacinat/koncit zatia za zaciatkoch/koncoch rovnakych kukuric,
         * pri nacitavani vstupu si vstup rozdelime na suvisle useky.
         * useky[c] je pole kde si pamatame ktore useky patria kukurici typu c.
         * counts[c][i] je pocet kukuric typu c ktore sme videli pred i-tym usekom typu c */
        vector<vector<int>> useky(n), counts(n);
        /* starts[i] =
         * (kde zacina i-ty usek, (typ kukurice na nom, na akom indexe ho najdeme v 'useky')) */
        vector<pair<int, ii>> starts;
        vector<int> count(n, 0);
        vector<int> pole;
        int maxc = 0;
        FOR(i, n) {
            int kuk;
            cin >> kuk;
            pole.push_back(--kuk);
            if (i) {
                if (kuk != pole[i - 1]) {
                    counts[kuk].push_back(count[kuk]);
                    useky[kuk].push_back(size(starts));
                    starts.push_back({i, {kuk, size(useky[kuk]) - 1}});
                }
            } else {
                counts[kuk].push_back(count[kuk]);
                useky[kuk].push_back(0);
                starts.push_back({i, {kuk, 0}});
            }
            count[kuk]++;
            maxc = max(maxc, count[kuk]);
        }

        int m = size(starts);
        starts.push_back({n, {-1, -1}});
        /* dp[z][k][p] = (vysledok od z-teho do k-tehu useku
         * ak nalavo je p nezozatych kukuric rovnakeho typu ako z-ty usek,
         * s ktorym najblizsim usekom napravo zozneme z-ty usek)
         */
        vector<vector<vector<ii>>> dp(
            m + 1, vector<vector<ii>>(m + 1, vector<ii>(maxc + 1, {0, -1})));
        int cnt = 0;
        for (int k = 0; k <= m; k++) {
            FOR(i, maxc + 1) dp[k][k][i].first = i * i;
            for (int z = k - 1; z >= 0; z--) {
                int typ = starts[z].second.first; // typ kukurice
                int index_useky = starts[z].second.second;
                FOR(p, counts[typ][index_useky] + 1) {
                    int len = starts[z + 1].first - starts[z].first + p;
                    ii& best = dp[z][k][p];
                    best = {len * len + dp[z + 1][k][0].first, k};
                    for (int i = index_useky + 1; i < size(useky[typ]) && useky[typ][i] < k; i++) {
                        int u = useky[typ][i];
                        best = max(best, {dp[z + 1][u][0].first + dp[u][k][len].first, u});
                        cnt++;
                    }
                }
            }
        }

        vector<ii> instructions;
        stack<pair<ii, ii>> to_resolve;
        to_resolve.push({{0, m}, {0, 0}});
        while (to_resolve.size()) {
            auto top = to_resolve.top();
            to_resolve.pop();
            int z = top.first.first;
            int k = top.first.second;
            int p = top.second.first;
            int from = top.second.second;
            if (z >= k) {
                if (p > 0)
                    instructions.push_back({starts[from].first + 1, starts[z].first});
                continue;
            }
            int instr = dp[z][k][p].second;
            if (instr == k) {
                instructions.push_back({starts[from].first + 1, starts[z + 1].first});
                to_resolve.push({{z + 1, k}, {0, z + 1}});
            } else {
                to_resolve.push({{instr, k}, {p + starts[z + 1].first - starts[z].first, from}});
                to_resolve.push({{z + 1, instr}, {0, z + 1}});
            }
        }

        cout << dp[0][m][0].first << " " << size(instructions) << "\n";
        for (ii a : instructions) {
            cout << a.first << " " << a.second << "\n";
        }
    }
}