h1(#beyond). 'Solutia':winter-challenge-2020/solutii/beyond problemei 'Beyond the Wall':problema/beyond_the_wall

h1(#hidden). 'Solutia':winter-challenge-2020/solutii/beyond problemei 'Beyond the Wall':problema/beyond_the_wall

Solutia va fi postata in curand.

h2. Ce este dualizarea?

Iata cateva cuvinte cheie: dualizare, quad-tree, lazy update.

Dualizarea este un concept folosit în geometrie prin care putem să transformăm un punct într-o dreaptă şi invers astfel încât oricărei teoreme din planul primal îi corespunde o teoremă din planul dual. Pentru mai multe detalii vă recomand următoarele linkuri: {"wikipedia":https://en.wikipedia.org/wiki/Duality_(projective_geometry)} , "Point‐Line Duality":https://www.cs.tulane.edu/~carola/teaching/cmps6640/spring16/slides/Point-Line%20Duality.pdf
 
O proprietate a spaţiului dual este că dacă în plan primal un punct $A$ se află sub dreapta $d$ atunci în plan dual punctul $D$ se află sub dreapta a ({$D$} este punctul obţinut din dreapta $d$, iar a este dreapta obţinută din punctul $A$)
 
h3. Demonstraţie:
 
În primul rând un punct $A(x{~A~}$, $y{~A~})$ se află sub dreapta $d: y = mx + b$ doar dacă $mx{~A~} - y{~A~} + b > 0$
Să persupunem că avem punctul A de coordonate (x{~A~}, y{~A~}) şi dreapta d de ecuaţie y = mx+b astfel încât X se află sub dreaptă.
Deci $mx{~A~} - y{~A~} + b > 0$.
În plan dual $A$ devine a cu ecuaţia: $y = x{~A~}x - y{~A~}$ iar $d$ devine $D$ de coordonate $(m, -b)$.
Înlocuind în formula de mai sus obţinem:
$x{~A~}m - y{~A~} - (-b) > 0$
$x{~A~}m - y{~A~} + b > 0$ (echivalentă cu cea din planul primal)
 
 
h2. Pentru $65$ de puncte:
 
În primul rând vom aplica principiul dualizării şi obţinem q puncte şi n drepte. Acum pentru fiecare punct trebuie să numărăm câte drepte trec pe deasupra lui. Mergând de la stânga la dreapta pe axa $O{~x~}$ şi sortând dreptele după înălţimea în acel $X$ vom observa că există maxim $n^2^$ permutări ale acestor drepte. Acest fapt se întâmplă deoarece oricare două drepte se intersectează maxim o dată. Putem să determinăm punctele în care fiecare pereche de drepte se intersectează şi să le sortăm. Astfel putem să construim permutările în $O(n^2^ * log(n))$. Parcurgem punctele de la stânga la dreapta şi facem swap-urile necesare în permutare. Pentru fiecare punct putem să căutăm binar câte drepte se află deasupra lui deoarece acestea vor fi sortate după înălţime.
Pentru 65 de puncte este nevoie însă de încă o optimizare. Cum $X_MAX$ este destul de mic se poate folosi Count Sort pentru a reduce complexitatea de generare a permutărilor la $O(n^2^)$. Detaliile rămân ca tema cititorului.
 
h2. Pentru $100$ de puncte:
 
Pentru a obţine punctaj maxim avem nevoie de o structură de date care să gestioneze în mod eficient punctele. Putem să folosim un Quad-Tree care la fiecare pas împarte planul în 4 cadrane cu număr aproximativ egal de puncte. În fiecare nod reţinem câte puncte se află în cadranul corespunzător. Complexitatea pentru construcţia arborelui este $O(n * log(n))$ dacă la fiecare pas este împărţit doar cel mai mic dreptunghi care conţine punctele din nodul actual. Pentru query observăm că o dreaptă nu poate să taie mai mult de 3 cadrane deci la fiecare pas putem să eliminăm cel puţin unul dintre acestea şi să mergem recursiv în cadranele care nu se află complet sub dreaptă. Complexitatea acestui query respectă formula $T(n) = 3 * (T(n / 4)) + O(1)$ deoarece merg recursiv în maxim 3 cadrane care au aproximativ $n / 4$ puncte, deci, din {"Master Theorem":https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)}, $T(n) = O(n^log{~4~}3^)$. Complexitatea finală este $O(n * log(n) + q * n^log{~4~}3^)$.
Pentru $100$ de puncte trebuie să mai facem o optimizare. Putem să generăm răspunsurile pentru fiecare query în plan dual. Astfel în Quad-Tree vom pune punctele de query şi pentru fiecare dreaptă o să facem lazy update pe cadranele complet aflate sub dreaptă. La final trebuie decât să mai parcurgem o dată arborele pentru a extrage răspunsul pentru fiecare query. Astfel complexitatea finală devine $O(n * log(n) + n * q^log{~4~}3^)$. Deşi complexitatea teoretica pare că este destul de mare, acest algoritm se comportă foarte bine în practică.