USACO nov 2005, divizia GOLD

(Categoria Competitii, autor(i) Adrian Diaconu)

Etapa din noiembria a fost una destul de usoara cu 17 punctaje maxime printre care si 3 romani:

  • Tiberiu Florea
  • Catalin Tiseanu
  • Adrian Vladu

Teste si enunturile problemelor sunt disponibile in sectiunea Download.

Asteroids

Vom rezolva aceasta problema folosind un algoritm de cuplaj maxim. Se va construi un graf bipartit in care vom avea pe o parte coloanele matricii (1..n) pe cealalta liniile matricii (1..m). Vom avea muchie de la o linie la o coloana daca in pozitia respectiva se afla un bolovan ce trebuie distrus. Graful astfel construit va avea n+m noduri si k muchii (locurile unde sunt plasati bolovanii). Problema se reduce astfel la determinarea unui suport minim pe un graf bipartit care este echivalenta cu gasirea cuplajului maxim pe acest graf. Suportul minim inseamna o multime de noduri de cardinal minim astfel incat fiecare muchie are cel putin un capat in multime.

Pentru cei care nu sunt familiarizati cu algoritmul de cuplaj pot folosi un algoritm de flux maxim adaugand o sursa virtuala legata de toate nodurile ce reprezinta coloanele si o destinatie legata de toate nodurile ce reprezinta liniile. Capacitatile vor fi toate 1. Fluxul maxim astfel determinat va fi egal cu cuplajul maxim. Complexitatea algoritmului de flux este O(Flux*(nr_noduri+nr_muchii)) si avand in vedere faptul ca fluxul poate fi maxim n (deoarece o coloana nu se poate cupla de doua ori) se ajunge la O(n*(n+m+k)).

Grazing on the Run

Rezolvarea acestei probleme se face folosind metoda programarii dinamice. Se vor sorta coordonatele la care se afla lucrurile pe care doreste Bessie sa le culeaga apoi se vor construi matricile mini,j,k si timpi,j,k care vor avea urmatoarele semnificatii:

  • mini,j,k - va retine costul necesar culegerii lucrurilor de pe pozitiile i, i+1, ... , j la care se adauga timpul la care s-s terminat culesul acstor lucruri inmultit cu numarul de obiecte ramase ( N - i + j - 1 ) deoarece la acestea se va ajunge minim la timpul respectiv. K va avea valoare 0 sau 1 in functie de capatul la care se afla Bessie la final ( stanga respectiv dreapta)
  • timpi,j,k - va retine timpul necesar culegerii obiectelor i, i+1, ..., j pentru a obtine minimul din mini,j,k

Se observa ca in configuratia (i,j,k) se ajunge din starile (i,j-1,1), (i,j-1,0), (i+1,j,1), (i+1,j,0). Complexitatea de completare a matricii va fi O(n2), in finala afisad minimul dintre min1,n,0,min1,n,1. Memoria necesara va fi de O(n) deoarece procesand matricea in ordinea cresterii lungimii intervalului (i,j) ne va fi necesara doar coloana precedenta.

Walk the Talk

Vom rezolva independent problema pentru fiecare cuvant aflat in dictionar. Vom nota ai,j matricea cu litere, iar si cuvantul pe care il analizam la un anumit moment, acesta avand lungimea L. Vom construi matricea sumi,j,k in care se va retine numarul de moduri in care se obtine secventa s1, s2, ... , sk folosind doar dreptungiul cu colturile in (1,1) si (i,j) din matricea de litere. Pentru a calcula configuratia (i,j,k) se numara intai cate se obtin pentru secventa 1..k pentru dreptunghiul respectiv fara a considera casuta (i,j) (sumi-1,j,k+sumi,j-1,k-sumi-1,j-1,k) apoi daca avem ai,j=sk adunam cate solutii avem pentru secventa 1..k-1 pentru dreptunghiul respectiv mai putin casuta (i,j) (sumi-1,j,k-1+sumi,j-1,k-1-sumi-1,j-1,k-1). In final solutia se va afla in sumn,m,L. Complexitatea construirii fiecare configuratii in parte este O(1) deci in total va fi O(n*m*L). Memoria necesara este O(n*m*L), dar aceasta se poate reduce la O(n*m) daca luam in considerare faptul ca la fiecare moment ne este necesar doar numarul de solutii pentru o secventa cu 1 mai mica.