Soluţii Summer Challenge 2009, Runda 3

• Lista de probleme
• Easy Choice
• Poligon3
• Copaci3
• Negustori

Easy choice

Pentru rezolvarea problemei, vom sorta mai întâi crescător şirul înălţimilor. Se poate observa uşor că o divizie va fi un interval compact în şirul sortat, de lungime C. Ne propunem să alegem R astfel de intervale care să nu se suprapună şi care să minimizeze dezechilibrul armatei.

Vom fixa printr-o căutare binară dezechilibrul D şi vom verifica dacă se pot plasa cel puţin R intervale disjuncte, fiecare cu dezechilibru cel mult D. Această verificare se poate realiza prin metoda programării dinamice, observând relaţia

• A[i] = max(A[i - 1], A[i - C] + 1), dacă H[i] - H[i - C + 1] ≤ D
• A[i] = A[i - 1], altfel

unde A[i] = numărul maxim de divizii cu dezechilibru cel mult D ce se pot crea folosind doar primii i candidaţi, iar H = şirul sortat al înălţimilor.

Complexitatea rezolvării de mai sus este O(N * log N + N * log H).

Poligon3

Vom fixa pe rând fiecare punct din cele N date ca cel mai din stânga şi, în caz de egalitate, cel mai de sus punct ce poate fi pe poligon. După ce am fixat un anume punct de referinţă, ne mai interesează doar punctele cu absicsa strict mai mare sau cu abscisa mai mare sau egală şi ordonata strict mai mică ca a punctului fixat. Notăm punctul de referinţă cu 0. Sortăm punctele rămase în funcţie de panta segmentului pe care îl formează cu punctul de referinţă. Vom parcurge punctele rămase în această ordine şi folosind metoda programării dinamice vom construi o matrice C[i][j] = aria maximă a unui poligon care are ultimele două vârfuri în punctele j şi i. Recurenţa este C[i][j] = max{C[j][k] + Arie(0, i, j) | i, j, k păstrează forma convexă a poligonului şi triunghiul (0, i, j) nu conţine nici un alt punct în interior}. Testul de păstrare a convexităţii este explicat pe larg în acest articol. Verificarea ca triunghiul 0, i, j să nu conţină nici un alt punct se poate face in O(1) cu ajutorul unei preprocesari, conducând la o complexitate totală de O(N⁴).
Pentru a obţine complexitatea O(N³), vom modifica semnificaţia matricii astfel: C[i][j] = $ aria maxima a unui poligon ce are ultimul vârf în punctul $i şi penultimul vârf în unul dintre punctele dintre 1 şi j. Având un punct i fixat ca ultimul vârf al poligonului până în momentul respectiv, vom determina acele puncte j pentru care triunghiul (0, i, j) nu conţine nici un punct în interior. Punctul i-1 se află mereu printre aceste puncte j, deoarece este imposibil să existe vreun punct în triunghiul (0, i-1, i) din cauza sortării iniţiale. Apoi vom determina restul punctelor j cu o parcurgere în ordine inversă şi bazându-ne pe observaţia ca următorul punct j pe care îl vom determina va verifica testul de păstrare al convexităţii relativ la punctul i şi la ultimul punct de tip j pe care l-am determinat pâna acum. Punem toate aceste puncte j in multimea s în ordinea sortării (sau în ordinea inversă determinării lor). Recurenţa devine C[i][s_k] = max{C[i][s_k-1], C[s_k][s_k-1] + Arie(0, s_k, i)}.

Copaci3

O prima observatie pe care o putem face este faptul ca daca diferenta dintre primul si ultimul copac este mai mare decat N * D atunci nu exista solutie. Pentru celelalte cazuri putem construi o dinamica D[i][j] insemnand costul minim pentru a aduce copacul i la inaltimea j, iar primi i copaci formeaza o configuratie estetica. O implementare brute force a acestei solutii are complexitate O(N * H²) putand fi redusa la O(N * H) folosind un deque pentru a calcula recurenta. Aceasta solutie ar fi adus ~20 de puncte.
Pentru 100 de puncte se observa faptul ca singurele inaltimi care conteaza sunt inaltimile de forma H[i] * X unde X se afla in intervalul [-N...N]. Astfel ajungem la N² inaltimi care conteaza, si astfel putem aduce solutia O(N * H) la complexitatea O(N³).

Negustori

Vom rezolva problema folosind metoda programării dinamice.

Pornim de la reprezentarea unei modalităţi de repartizare a tuturor celor n negustori la cele n locaţii de pe aleea comercială. O repartizare presupune să avem 0 sau mai mulţi negustori străini plus cei locali repartizaţi la locaţia 1, 0 sau mai mulţi negustori străini plus cei locali la locaţia 2, etc. Ulterior, negustorii se vor deplasa spre următoarele poziţii spre finalul aleii pentru a găsi un loc liber. Astfel, o stare constă în completarea cu negustori a locurilor k, .., n, rămânând m locuri libere pentru completări ulterioare.

Fie numărul de repartizări ale negustorilor pe locurile k, .., n, rămânând m locuri libere. Vom face următoarele notaţii: l[k] numărul de negustori locali care preferă locaţia k, cl[k] numărul de negustori locali care preferă una din locaţiile între 1 şi k (cl[k] = l[1] + .. + l[k]). Pentru a calcula , ne rămâne să repartizăm negustori străini pe locul k-1 pe lângă cei l[k-1] negustori locali. Această repartizare se realizează în limita locurilor disponibile. Numărul locurilor disponibile este egal cu locuriLibere = m+1-l[k-1] (cele m locuri libere la care adăugăm locul k-1 şi scădem pe cele ocupate de negustorii locali, l[k-1]). Numărul total de negustori străini rămaşi se obţine scăzând din numărul total de negustori pe cei repartizaţi pe locaţiile k, .., n şi pe cei locali repartizaţi pe una din locaţiile preferate dintre 1, .., k-1, adică negustoriStraini = n-(n-k+1-m)-cl[k-1]. Astfel, numărul total de negustori străini este m+k-1-cl[k-1]. Rezultă că vom alege i negustori străini, fără a depăşi numărul locurilor libere, pe care îi vom repartiza pe poziţia k-1. Astfel, recurenţa este: . Avem . Rezultatul se găseşte în .

Complexitatea soluţiei: O(n³).