GTA

Na autorské práva útočiaci príbeh tohoto príkladu skrýval úlohu nájdenia počtu kostier jednoduchého súvislého grafu s relatívne malým počtom vrcholov. Skúsenejší súťažiaci si správne uvedomili, že úlohy podobného charakteru sú dobre preskúmané a hľadali informácie o riešení na Internete.

A skutočne, je relatívne jednoduché nájsť napr. článok na Wikipédii popisujúci kompletné riešenie.

Jedinou komplikáciou je výpočet determinantu matice v modulárnej aritmetike. Je nevhodné používať typy s plávajúcou desatinnou čiarkou, pretože môže dochádzať k strate presnosti. Z tohoto dôvodu a vďaka faktu, že počet vrcholov grafu bol relatívne malý, je vhodné použiť na výpočet determinantu dynamické programovanie.

Determinat vypočítame s časovou náročnosťou O( N × 2N ) a pamäťovou O( 2N ) len s použitím operácie sčítanie. Toto riešenie vychádza z Leibnizovej definície determinantu, ktorá ho definuje ako sumu vnútorných súčinov všetkých permutácií buniek matice takých, že žiadna dvojica z nich sa nenachádza v rovnakom riadku alebo stĺpci. Tieto súčiny sa do sumy zarátavajú so znamienkom odzrkadlujúcim paritu počtu inverzií v príslušnej permutácii. Inverzia je počet dvojíc čísiel P[i] a P[j], pre ktoré platí P[i] < P[j] a zároveň i > j. Nepárnemu počtu inverzií prislúcha záporné znamienko a naopak.

Algoritmus dynamického programovania bude mať stavový priestor s dimenziami:

DP[použité stĺpce poznačené v bitmaske][parita počtu inverzií]

A rekurzívna relácia (uvedená bez modulo 109 + 9 kvôli prehľadnosti):

DP[ M ∪ i ][ (I + početInv(M)) mod 2 ] += MATICA[ |M| ][ i ] * DP[ M ][ I ]

Výsledok nakoniec vypočítame spojením medzivýsledkov pre obe znamienka:

DP[ množina všetkých stĺpcov matice ][0] - DP[ množina všetkých stĺpcov matice ][ 1 ]

Poradie iterácie je zrejmé z priloženého vzorového riešenia. Za povšimnutie stojí fakt, že index aktuálne spracovávaného riadku je totožný s počtom prvkov M, pretože pre každý riadok pridáme do M práve jeden stĺpec.

Vypracoval: Daniel Švoňava

Zdroj príkladu: Sphere Online Judge