Zadanie
Kiribatské pobrežie začali nedávno sužovať nájazdy útočných sépií. Sépie priplávajú ku brehu a potom sťahujú do mora slnečníky, lehátka a výletníkov. Minule dokonca odtiahli aj stánok so zmrzlinou.
Určite netreba vysvetľovať, čo by sa stalo s turistickým ruchom, ak by sa to rozkríklo. Kiribatská pobrežná stráž preto rýchlo dostala z príslušného ministerstva dotáciu a dôraznú inštrukciu, nech problém rýchlo vyrieši.
Za peniaze z ministerstva pobrežná stráž nakúpila \(n\) balíst. Balista je mechanické zariadenie, schopné strieľať harpúny po sépiách. Harpúna má samozrejme na sebe uviazané lano, takže trafenú sépiu vie pobrežná stráž vytiahnuť na breh (a tam naporcovať a zjesť).
Úloha
Pobrežie Kiribati si predstavíme ako os \(x\), more bude polrovina zodpovedajúca kladnému \(y\). Na pobreží stojí \(n\) balíst. Z mora sa práve blíži \(n\) sépií. Každú balistu aj každú sépiu považujeme za bod.
Pobrežná stráž by chcela uloviť všetkých \(n\) sépií naraz. Je zjavné, že na to treba každou balistou uloviť inú sépiu. Existuje teda \(n!\) možností, ako priradiť balisty ku sépiám.
Nie všetky možnosti sú však vhodné. Problém je, že keby sme strieľali len tak hala-bala, mohli by sa nám niektoré laná z harpún o seba zamotať. Pobrežná stráž preto musí strieľať takým spôsobom, aby sa tejto nepríjemnosti zaručene vyhla.
Presnejšie: Keď trafíme sépiu harpúnou, lano uviazané o harpúnu tvorí úsečku spájajúcu balistu na brehu s trafenou sépiou vo vode. Priradenie balíst sépiám je dobré vtedy, ak sú všetky tieto úsečky navzájom disjunktné (čiže ak žiadne dve nemajú spoločný bod).
Dané sú súradnice balíst aj sépií. Spočítajte, koľko existuje dobrých priradení balíst sépiám. Vypíšte túto hodnotu modulo \(10^9 + 7\).
Dôležité: V tejto úlohe nie je nutné optimalizovať časovú zložitosť. Presnejšie, ľubovoľné riešenie s polynomiálnou časovou zložitosťou môže dostať plný počet bodov za popis – ale samozrejme, na plný počet bodov musíte riešenie dobre popísať a ukázať o ňom, že naozaj má polynomiálnu časovú zložitosť.
Formát vstupu
V prvom riadku vstupu je celé číslo \(n\). Platí \(1\leq n\leq 50\).
V druhom riadku vstupu je \(n\) celých čísel \(b_1,\dots,b_n\): x-ové súradnice balíst. Balista \(i\) sa teda nachádza na súradniciach \((b_i,0)\).
V treťom riadku je \(n\) celých čísel \(x_1,\dots,x_n\): x-ové súradnice sépií.
Vo štvrtom riadku je \(n\) celých čísel \(y_1,\dots,y_n\): y-ové súradnice sépií.
Všetky súradnice sú od \(-1000\) do \(1000\), vrátane. Všetky \(y_i\) sú navyše kladné. Žiadne dve balisty ani žiadne dve sépie sa nenachádzajú v tom istom bode.
Formát výstupu
Vypíšte jeden riadok a v ňom hodnotu \((p\bmod 10^9 + 7)\), kde \(p\) je počet dobrých priradení balíst sépiám.
Príklady
Input:
2
4 -4
1 2
1 2
Output:
2
Balisty sú na súradniciach \((4,0)\) a \((-4,0)\). Sépie sú na súradniciach \((1,1)\) a \((2,2)\). Sú dve možné priradenia balíst sépiám. Obe sú dobré.
Input:
2
4 -4
4 -4
10 10
Output:
1
Tentokrát je len jedno priradenie balíst sépiám dobré, pri druhom sa laná prekrížia.
Input:
3
-1 0 1
0 0 0
1 2 3
Output:
2
Všimnite si, že sú zakázané aj situácie, v ktorých koniec jednej úsečky leží na inej úsečke. (Inými slovami, lano ide priamo ponad inú sépiu.)
Input:
4
-2 2 98 102
0 1 100 101
1 2 1 2
Output:
4
Input:
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
Output:
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;
}
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ť.