Note de curs, probleme algoritmică, 15 noiembrie 2013

În acest curs am discutat problemele:

• 1560 - Elementary Symmetric Functions;
• 1486 - Equal Squares;
• 1934 - Black Spot;
• 1215 - Exactness of Projectile Hit.

1560 - Elementary Symmetric Functions

Problema se rezolvă cu ajutorul arborilor de intervale. Partea dificilă a problemei este:

• stabilirea valorilor care trebuie calculate pentru fiecare nod al arborelui;
• determinarea funcției de "combinare" a două subintervale adiacente.

Fiecare nod reprezintă o subsecvență a vectorului A. Pentru fiecare subsecvență menținem cerința problemei: valorile S(0), S(1), S(2), S(3), S(4).

Cunoscând valorile din fiul stâng (Sst(0), Sst(1), Sst(2), Sst(3), Sst(4)) și din fiul drept (Sdr(0), Sdr(1), Sdr(2), Sdr(3), Sdr(4)) al unui nod putem calcula valorile sale (S(0), S(1), S(2), S(3), S(4)) cu formulele:

• S(0) = Sst(0) * Sdr(0)
• S(1) = Sst(0) * Sdr(1) + Sst(1) * Sdr(0)
• S(2) = Sst(0) * Sdr(2) + Sst(1) * Sdr(1) + Sst(2) * Sdr(0)
• S(3) = Sst(0) * Sdr(3) + Sst(1) * Sdr(2) + Sst(2) * Sdr(1) + Sst(3) * Sdr(0)
• S(4) = Sst(0) * Sdr(4) + Sst(1) * Sdr(3) + Sst(2) * Sdr(2) + Sst(3) * Sdr(1) + Sst(4) * Sdr(0)

1486 - Equal Squares

Valoarea K, lungimea maximă a laturilor unei perechi de sub-pătrate identice se poate găsi prin căutare binară, cu condiția să avem la dispoziție o funcție care ne spune, pentru o lungime fixată a laturii dacă există o astfel de pereche.

Calculăm cheia hash asociată fiecărui sub-pătrat de latură fixată folosind tehnica de rolling hash. Dacă găsim cel puțin două sub-pătrate cu aceeași cheie hash spunem (cu o probabilitate suficient de mare) că există o pereche căutată cu latura fixată.

Tehnica de rolling hash se va aplica succesiv, mai întâi pe fiecare linie, pentru subsecvențe de caractere de o lungime fixată și apoi pe coloane, pentru sub-pătrate de o latură fixată.

1934 - Black Spot

Pentru fiecare dintre drumurile posibile se cunoaște p - probabilitatea de a-l întâlni pe Kraken.

Esențial în rezolvarea problemei este: cunoscând p1 și p2, probabilitatea de a-l întâlni pe Kraken pe drumurile d1 respectiv d2, care este probabilitatea de a-l întâlni pe Kraken parcurgând succesiv drumurile d1 și d2?

p12 = 1-(1-p1)*(1-p2)

Folosind această formulă pentru compunerea drumurilor, problema se poate rezolva printr-un algoritm de drum de cost maxim.

1215 - Exactness of Projectile Hit

Dacă punctul dat se află în interiorul poligonului, atunci distanța va fi 0.

Altfel, se va calcula distanța de la punct la fiecare dintre segmentele care definesc poligonul și se va alege cea mai mică dintre distanțe.