8. Obrana pobrežia vzorové riešenie

2
4 -4
1 2
1 2

2

2
4 -4
4 -4
10 10

1

3
-1 0 1
0 0 0
1 2 3

2

4
-2 2 98 102
0 1 100 101
1 2 1 2

4

9
5 7 8 9 10 11 12 15 18
13 4 1 6 12 7 9 17 5
15 7 11 2 15 1 6 4 5

10

Už v úlohe 8 minulej série sme sa stretli s elementárnou operáciou, ktorá nám bude užitočná aj tu: dozvedeli sme sa, ako pomocou vektorového súčinu ľahko a presne zistiť, či sa dve úsečky pretínajú. Toto budeme potrebovať aj v tejto úlohe. Kto to už zabudol, nájde to v Kuchárke.

Hrubá sila

Akonáhle máme takúto funkciu, už vieme riešiť zadanú úlohu hrubou silou: postupne vyskúšame všetkých \(n!\) permutácií, každú z nich skontrolujeme, a spočítame tie, pre ktoré sa žiadne dve úsečky nepretínajú. Za takéto riešenie síce nebude plný počet bodov, ale ak ste za túto úlohu mali nulu, tak aj toto je od nuly lepšie. A je to naozaj pár riadkov programu – napr. v C++ máme k dispozícii funkciu next_permutation pomocou ktorej sa skúšanie permutácií implementuje ozaj hravo.

Chceme lepšie

My ale chceme nejaké riešenie, ktoré bude bežať v polynomiálnom čase. Ako na to?

Naše riešenie je založené na nasledujúcom pozorovaní: Zoberme sépiu, ktorá je najďalej od pobrežia. (Ak je takých viac, tak trebárs tú z nich, ktorá má najmenšie číslo.) Položme si teraz otázku: môže byť táto sépia trafená balistou číslo \(k\)? Odpoveď je jednoduchá: áno, ak sú splnené nasledujúce podmienky.

• Na úsečke medzi balistou \(k\) a našou sépiou neležia žiadne iné sépie.

• “Naľavo” od našej úsečky je rovnako veľa balíst ako sépií (a napravo teda nutne tiež).

Postupne vyskúšame všetky možnosti pre \(k\). Vždy, keď nájdeme nejakú vyhovujúcu, tak sme vlastne pôvodný problém rozdelili na dva menšie: Nech \(a\) je počet spôsobov, ktorými vieme spárovať sépie a balisty naľavo od našej úsečky a nech \(b\) je počet spôsobov, ktorými to vieme urobiť napravo. Potom dokopy dostávame \(ab\) riešení, lebo každé riešenie vľavo vieme skombinovať s každým riešením vpravo.

No a ak sme už zvlášť pre každé \(k\) určili, koľko mu zodpovedá riešení, tak celkový počet riešení je jednoducho súčtom všetkých týchto počtov.

Vyššie popísané riešenie nás teda vedie k rekurzívnemu riešeniu našej úlohy: vyskúšame nejaké možnosti ako spraviť jednu dvojicu balista-sépia a následne sa rekurzívne zavoláme na nejaké menšie vstupy.

Ostáva ale celkom veľa nezodpovedaných otázok. Funguje to vôbec? A ak áno, má to polynomiálnu časovú zložitosť?

Funguje to vôbec?

To, že vyššie uvedené riešenie funguje, je spôsobené práve našou šikovnou voľbou sépie, ktorej pár hľadáme ako prvý. My sme si zvolili sépiu \(S\), ktorá je najďalej od pobrežia, a spojili sme ju s nejakou balistou \(B\) na pobreží. Ak teraz zoberieme hocijakú sépiu naľavo od \(S\) a spojíme ju s balistou napravo od \(B\) (alebo naopak), bude táto nová úsečka určite križovať úsečku \(SB\). Vďaka našej šikovnej voľbe sépie sa nám teda naozaj nakreslením úsečky \(SB\) zadanie rozpadne na dve časti ktoré sú nezávislé.

Má to polynomiálnu časovú zložitosť?

Nemá. Generuje to postupne po jednom všetky prípustné riešenia, a tých ani omylom nemusí byť len polynomiálne veľa. (Ľahko sa vyrobí napríklad vstup, ktorý bude mať riešení aspoň \(2^{n/2}\). Viete dosiahnuť ešte viac?)

Ako teda dostať polynomiálne riešenie?

Jednoducho: pridáme memoizáciu. Každý konkrétny podproblém, na ktorý narazíme (“tu je podmnožina sépií a úsek balíst, koľkými spôsobmi ich vieme pospájať?”) budeme riešiť len raz. Keď ho prvýkrát vyriešime, zapamätáme si jeho riešenie. Ak by sme na ten istý podproblém narazili inokedy, už nebudeme nič skúšať, len sa pozrieme na jeho zapamätané riešenie a to vrátime na výstup.

Prečo pridaním memoizácie dostaneme polynomiálne riešenie?

Kvôli konzistencii si predstavme, že naľavo aj napravo od celého vstupu je po jednej sépii (ďaleko na mori) a jednej baliste. Ľubovoľný konkrétny podproblém si teraz môžeme popísať tak, že povieme dve úsečky sépia-balista: jedna tvorí jeho ľavý a druhá jeho pravý okraj.

Všetkých podproblémov je teda nanajvýš toľko, koľko je takých dvojíc úsečiek – teda \(O(n^4)\), lebo máme \(n\) možností pre každý koniec každej úsečky. V skutočnosti bude dosiahnuteľných podproblémov výrazne menej. Na dôkaz polynomiálnej časovej zložitosti nám ale stačí takýto horný odhad ich počtu.

No a konkrétny podproblém vyriešime v \(O(n^2)\): najskôr overíme, či máme rovnako veľa sépií a balíst (ak nie, odpoveď je 0), potom nájdeme najvzdialenejšiu sépiu, a potom ju postupne vyskúšame spojiť s každou balistou. Keď máme konkrétnu dvojicu sépia-balista, potrebujeme ešte prejsť všetky ostatné a rozdeliť ich na ľavé a pravé (a skontrolovať, že žiadna sépia neleží na práve nakreslenej úsečke).

Celkovo teda dostávame riešenie s časovou zložitosťou \(O(n^6)\).

Šlo by aj zlepšiť. Napríklad tak, že keď už máme zvolenú najvzdialenejšiu sépiu, tak si všetky ostatné balisty a sépie okolo nej polárne usporiadame, aby sme vedeli rýchlejšie hovoriť, ktoré objekty sú naľavo a ktoré napravo od práve skúšanej úsečky sépia-balista. Zadanie však hovorí, že čokoľvek polynomiálne je dobré, a tak budeme leniví a nebudeme už nič zlepšovať.

Implementácia

V mojej implementácii som bol extra lenivý, preto si konkrétny podproblém reprezentujem nie pomocou štyroch čísel (dve balisty a dve sépie) ale pomocou dvoch 64-bitových intov: v jednom sú nastavené bity pre tie harpúny, ktoré ešte mám, a v druhom bity pre sépie. Ono je to skoro jedno, stavov mám stále rovnako a takto sa ten kód stručnejšie písal.

Namiesto 4-rozmerného poľa potom používam na memoizáciu map. Tým mi pribudne v časovej zložitosti ešte logaritmus navyše. Spomínal som už, že som bol extra lenivý? :)

Navyše sa ani neobťažujem priebežne kontrolovať, či mám rovnako veľa sépií a balíst. Až ak na konci vetvy rekurzie zistím, že jedny sa už minuli a druhé ešte nie, vrátim nulu.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
vector<ll> B, X, Y;

map< pair<ll,ll>, int > memo;

// vektorový súčin: kladný ak (x3,y3) leží naľavo ak sa pozeráme z (x1,y1) na (x2,y2)
ll cross_product(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
    ll ux = x2-x1, uy = y2-y1, vx = x3-x1, vy = y3-y1;
    return ux*vy - vx*uy;
}

int vyries(ll balisty, ll sepie) {
    pair<ll,ll> key = {balisty,sepie};
    if (memo.count(key)) return memo[key]; // tento problém sme už riešili

    int &odpoved = memo[key]; // spravíme si referenciu na záznam v mape kam chceme zapísať odpoveď

    // zistíme, či už sme na konci
    if (balisty == 0 && sepie == 0) return odpoved = 1;
    if (balisty == 0 || sepie == 0) return odpoved = 0;

    // tu by sa dalo rovno kontrolovať, či máme balíst a sépií rovnako veľa
    // pridanie nasledujúceho riadku výrazne urýchli čas behu v praxi
    // if (__builtin_popcountll(balisty) != __builtin_popcountll(sepie)) return odpoved = 0;

    // nájdeme najvzdialenejšiu sépiu
    int bests = -1;
    for (int s=0; s<N; ++s) if (sepie & 1LL << s) if (bests == -1 || Y[s] > Y[bests]) bests = s;

    // vyskúšame všetky možné balisty
    odpoved = 0;

    for (int b=0; b<N; ++b) if (balisty & 1LL << b) {
        // rozdelíme zvyšok na ľavú a pravú stranu, skontrolujeme že nič neleží na úsečke
        bool ok = true;
        ll slave = 0, sprave = 0, blave = 0, bprave = 0;

        for (int i=0; i<N; ++i) if (i != bests) if (sepie & 1LL << i) {
            ll poloha = cross_product( B[b], 0, X[bests], Y[bests], X[i], Y[i] );
            if (poloha > 0) slave |= 1LL << i;
            if (poloha < 0) sprave |= 1LL << i;
            if (poloha == 0) ok = false;
        }

        for (int i=0; i<N; ++i) if (i != b) if (balisty & 1LL << i) {
            ll poloha = cross_product( B[b], 0, X[bests], Y[bests], B[i], 0 );
            if (poloha > 0) blave |= 1LL << i;
            if (poloha < 0) bprave |= 1LL << i;
        }

        if (ok) odpoved = (odpoved + vyries(blave,slave) * vyries(bprave,sprave)) % 1000000007;
    }
    return odpoved;
}

int main() {
    cin >> N;
    B.resize(N); for (auto &b:B) cin >> b;
    X.resize(N); for (auto &x:X) cin >> x;
    Y.resize(N); for (auto &y:Y) cin >> y;
    ll vsetko = (1LL << N) - 1;
    cout << vyries(vsetko,vsetko) << endl;
}