Solutia problemei Beyond the Wall

Ce este dualizarea?

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 , Point‐Line Duality

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)

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_Ax - y_A iar d devine D de coordonate (m, -b).
Înlocuind în formula de mai sus obţinem:
x_Am - y_A - (-b) > 0
x_Am - y_A + b > 0 (echivalentă cu cea din planul primal)

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² 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² * 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²). Detaliile rămân ca tema cititorului.

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 Theoreme, T(n) = O(n^log₄3). Complexitatea finală este O(n * log(n) + q * n^log₄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₄3). Deşi complexitatea teoretica pare că este destul de mare, acest algoritm se comportă foarte bine în practică.