Programare dinamică cu structuri de date

Introducere

Programarea dinamică și structurile de date reprezintă două dintre capitolele cele mai populare în rândul elevilor, precum și în rândul problemelor date la competiții, de multe ori acestea formează o parte esențială a seturilor de probleme și de cunoștințe care departajează cei mai buni concurenți la olimpiade și concursuri.

În multe situații, atunci când ne gândim la soluții care folosesc dinamici și alte recurențe similare, ajungem să ne gândim la optimizări care ne duc cu gândul la probleme care se pot rezolva ușor folosind structuri de date. Astfel, se dă naștere unui tip nou de probleme, dinamicile cu structuri de date.

În acest articol, vom prezenta câteva exemple de probleme, împreună cu modul în care aplicăm structurile de date și utilitatea îmbinării celor două seturi de cunoștințe. Fie că este vorba de structuri precum arbori de intervale, arbori indexați binar, stive, cozi sau deques, aceste tipuri de dinamici sunt foarte utile și importante de știut.

Problema exemplu - Projects

View Problem

CSES

Deschide

În această problemă, trebuie să alegem un număr de proiecte care nu se suprapun și ne aduc suma profiturilor maximă. Această problemă reprezintă o dinamică clasică, dar dat fiind faptul că avem restricții foarte mari, nu putem să o rezolvăm folosind metodele obișnuite. Astfel, vom avea nevoie să normalizăm mai întâi datele, iar mai apoi ne putem gândi la o recurență în care avem $dp\[i]$ ca fiind suma maximă a profiturilor pentru un proiect care se termină la al i-lea moment distinct de timp.

În mod evident, pentru a calcula această dinamică, vom avea nevoie de un maxim parțial pentru primele $j$ poziții, unde $j$ este poziția cea mai mare din șirul de momente de timp cu proprietatea că acel moment de timp nu se suprapune cu intervalul pe care îl alegem.

Pentru a optimiza această dinamică, vom putea folosi fie o structură de date (arbore de intervale sau indexat binar), fie chiar un maxim parțial care ar reduce și mai mult complexitatea soluției cerute.

Mai jos puteți găsi o soluție care obține accepted.

--8 < --"dificil/data-structures-dp/projects.cpp"

Problema Subsequences

View Problem

Codeforces

Could not fetch problem details

Deschide

În această problemă, trebuie să numărăm câte subșiruri crescătoare cu lungimea $k+1$ are șirul dat, iar o proprietate importantă este aceea că valorile formează o permutare a primelor $n$ numere naturale.

Deoarece lungimea căutată este mică, ne putem gândi la a păstra o dinamică pe două dimensiuni, care să ne păstreze numărul de subșiruri de lungime $i$ care se termină cu valoarea $j$.

Pentru a calcula această dinamică, vom vrea să știm pentru o pereche $(i, j)$ numărul de moduri corespunzătoare tuturor perechilor eligibile de forma $(i-1, x)$ cu proprietatea că $x \< j$, iar $poz\[x] \< poz\[j]$, unde $poz\[x]$ reprezintă unde apare $x$ în șirul dat.

Această recurență se poate din nou calcula relativ ușor folosind arbori de intervale sau arbori indexați binar, mai jos puteți găsi o soluție care rezolvă problema.

--8 < --"dificil/data-structures-dp/subsequences.cpp"

Problema Tulip Bouquet

View Problem

Kilonova

Could not fetch problem details

Deschide

Pentru a rezolva această problemă, ne putem gândi în primul rând la dinamica relativ simplă, dar înceată în $\mathcal{O}(n \cdot k^2)$ care are tranziții în $\mathcal{O}(k)$.

Obiectivul principal va fi să optimizăm această soluție, iar cel mai simplu mod de a face acest lucru este să ținem o stivă cu pozițiile cele mai relevante pentru tranzițiile noastre.

Chiar dacă acest lucru nu va fi îndeajuns, ne putem gândi un pas mai departe și să ținem pentru fiecare poziție relevantă din stivă maximul tuturor pozițiilor acoperite de acel interval, iar mai apoi pentru acele intervale, să ne gândim la un maxim parțial care să ne permită să păstrăm toate valorile maxime rapid și eficient.

Când unim două intervale, vom ține valorile maxime din fiecare din ele și apoi vom combina noile valori pentru a putea insera din nou acel răspuns în stivă.

Mai jos puteți găsi soluția de 100 de puncte, unde sunt mai multe detalii incluse.

--8 < --"dificil/data-structures-dp/bouquets.cpp"

Problema Pictures with Kittens

View Problem

Codeforces

Could not fetch problem details

Deschide

La o primă citire este evident faptul că putem găsi repede o dinamică de tipul $dp\[i]\[j]$ ca fiind suma maximă dacă pentru primele $i$ poziții, am folosit $j$ astfel de valori. Această recurență poate fi descrisă ca fiind maximul ultimelor $k$ poziții de pe coloana precedentă, $j-1$, lucru ce poate fi optimizat în modul cel mai eficient folosind o structură de date de tip deque, așa cum se poate vedea și în soluția prezentată mai jos.

--8 < --"dificil/data-structures-dp/kittens.cpp"

Problema Interstellar Intervals

View Problem

USACO

Deschide

Această problemă duce foarte repede cu gândul la o dinamică prin care putem număra câte șiruri distincte există cu proprietatea că toate restricțiile date până la un punct sunt respectate. Deoarece avem două tipuri de culori în practică (albastru și alb, roșu este dedus din pozițiile colorate în albastru), ne putem gândi mai întâi să păstrăm două dinamici, după cum urmează:

• $dp[i]$ = nr de moduri de a umple primele $i$ poziții dacă pe poziția $i$ avem albastru$
• $dp2[i]$ = nr de moduri de a umple primele $i$ poziții dacă pe poziția $i$ avem alb$

Soluția în $\mathcal{O}(n^2)$ este relativ simplă, pentru alb putem avea o tranziție de la $i-1$ la $i$, iar pentru albastru, putem fixa un interval și verificăm dacă îl putem plasa conform restricțiilor date, adăugând $dp\[x-1]$ dacă am putut plasa un interval între $x$ și $i$.

Pentru a optimiza soluția, putem observa pentru fiecare poziție $i$ cât de mult ne putem duce la stânga cu un interval din cauza restricțiilor colorate în roșu, precum și cât de mult ne putem duce la dreapta de la acea poziție din cauza restricțiilor colorate cu albastru.

După calcularea acestor valori, putem ține o structură de date (în soluția de mai jos, un AIB) care să țină suma valorilor de pe un interval pentru a putea folosi restricțiile cu albastru în avantajul nostru.

În cele din urmă, complexitatea devine $\mathcal{O}(n \log n)$. Puteți citi soluția de mai jos pentru mai multe detalii, precum și să vizionați videoul de mai sus.

--8 < --"dificil/data-structures-dp/interstellar.cpp"

Concluzii

Aceste probleme reprezintă o intersecție a două arii care sunt frecvent întâlnite la concursurile de algoritmică și nu numai. Cunoașterea celor mai frecvent întâlnite observații, împreună cu însușirea tipurilor de implementări face acest capitol important și util pentru studiul vostru individual.

Probleme suplimentare

• IIOT 2024 Planning Excursions
• ONI 2010 Stalpi
• RCPC 2023 Yet Another Colored Tree Problem
• Lot 2024 Juniori Pokemoni
• Codeforces WI-FI
• Codeforces Pathwalks
• ONI 2015 Baraj Seniori s2c
• ONI 2005 Baraj Seniori Evantai
• Codeforces Yunlin's Subarray Queries (hard)
• Codeforces Culture Code
• JOI 2022 Railway Trip 2
• Lot 2008 Seniori turnuri
• Probleme cu dinamici si structuri de date de pe Codeforces
• Probleme cu dinamica si deque de pe kilonova
• Alte probleme similare de pe kilonova

Resurse suplimentare

• Data Structures in Dynamic Programming Week - Codeforces
• Monotone Queue optimization - robert1003