Solutia problemei Pisica

Prima parte a rezolvarii problemei este data de gasirea inaltimii pisicii. Pentru a evada, pisica isi poate alege un unghi si o pozitie in interiorul custii sub care sa realizeze o translatie pentru a evada printre doua bare ramase consecutive. Practic, Pisica va fi incadrata de doua drepte paralele iar distanta dintre ele trebuie sa fie minima.

Pentru a minimiza distanta dintre cele doua drepte paralele care vor incadra pisica, e suficient sa incercam ca una din ele sa fie data de un segment a doua varfuri consecutive ale Pisicii. Se observa ca daca ne fixam segmentul, dreapta paralela care va incadra Pisica va atinge varful de pe Pisica aflat la cea mai mare distanta de dreapta aleasa.

Pentru calculcul inaltimii, e suficient sa tinem un indice la punctul care obtine aria cea mai mare cu cele doua puncte ale segmentului. Acest indice se muta odata cu schimbarea segmentului ales. Pentru fiecare segment, calculam distanta ca fiind aria celor trei puncte impartit la lungimea segmentului, si luand minimul tutoror acestor valori aflam inaltimea Pisicii. Astfel, obtinem in O(M) intaltimea dorita.

A doua parte a rezolvarii este data de alegerea varfurilor Custii, in asa fel incat fiecare doua puncte alese consecutive sa se afle la o distanta cel putin egala cu inaltimea Pisicii.

Pentru 60 de puncte

E suficient sa fixam in O(N) unul din punctele pe care le pastram. Pentru fiecare fixare, putem parcurge in O(N) toate punctele in ordine trigonometrica, luand decizia greedy daca pastram sau nu punctul - il vom pastra doar daca urmatorul punct ar fi la distanta prea mare de ultimul ales. Dintre toate variantele in care am fixat un punct, o alegem pe aceea care obtine solutia optima. Obtinem complexitatea de O(N^2).

Pentru 100 de puncte

Putem calcula urm[i] = punctul urmator din poligon pe care trebuie sa il pastrez daca pastrez punctul i. Datorita faptului ca poligonul este convex, urm[i + 1] este fie urm[i], fie mai incolo in sens trigonometric. Calculul sirului urm[] se poate realiza in O(N). Acest lucru e posibil tocmai pentru ca: Se garanteaza ca in situatia in care se pastreaza toate barele, pisica se poate roti/translata succesiv astfel incat sa atinga orice bara cu orice varf al ei.

Apoi putem folosi aceste salturi pentru a putea obtine rapid solutia optima in complexitate mai buna. De exemplu, putem tine d[i][j] = cat de mult ma extind in sens trigonometric daca fac 2ⁱ salturi de forma x -> urm[x] daca plec din j. Initializarea este d[ 0 ][i] = distantaTrigonometrica(i -> urm[i]) iar recurenta se realizeaza in O(1). Dupa aceasta precalculare de O(N * logN), putem afla in O(logN) care este numarul de puncte pe care trebuie sa le pastrez daca aleg sa il pastrez neaparat pe i. Luand pe rand toate valorile posibile ale lui i, aflam solutia optima.

Complexitate finala: O(M + NlogN) timp si O(M + NlogN) memorie. Mentionam ca exista si solutii liniare.