1046 Stalpisori

[•pauldb]

Aici puteti discuta despre problema Stalpisori.

[•APOCALYPTO]

Imi da si mie cineva un hint pentru solutia de 100?
Pana acum am facut n*log P[n]* log n.

Multumesc  anticipat!

[•blasterz]

Se poate in O(n log P[n]) . In loc sa cauti binar pentru P[ i ] + D si P[ i ] - D poti folosi o coada si obtii O(n) in loc de O(nlogn) la pasul cautarii binare

[•APOCALYPTO]

Se poate in O(n log P[n]) . In loc sa cauti binar pentru P[ i ] + D si P[ i ] - D poti folosi o coada si obtii O(n) in loc de O(nlogn) la pasul cautarii binare

10x!
+1 

[•Steve]

Solutia optima e O(N), nu mai merge O(N * log (P[N - 1])) oricate optimizari ai face, hope it helps.

[•vendetta]

Salut! Am rezolvare in O(log P[n] * n) si iau 70 de puncte. Ceva indicii pentru o complexitate mai buna ?

[•ctlin04]

Mie mi-a intrat in O( N log K ), dar vad ca intradevar se poate si in O ( N ),nu-ti voi da indiciu pentru O ( N ) pentru ca nu e solutia gindita de mine, iar petru N log K, pentru fiecare pozitie este evident ca ea trebue sa faca parte dintr-o segventa de k numere consecutive, presupunem mai intii ca capatul segventei se afla la dreapta pozitiei si cautam binar care este cel mai apropiat capat din dreapta, exact asa cautam si pentru capatul din stinga, iar apoi luam raza minima dintre aceste doua cazuri.
De exemplu pentru k=3 si segventa de sir 14 20 24 26 35, vrem sa calculam raza minima pentru numarul 24, mai intii daca capatul se afla la dreapta atunci putem lua doar segventa 24 26 35 si respectiv raza este 11, iar daca cautam la stinga vedem ca raza minima este 6, respectiv pentru a include elementul 24 intr-o segventa de k numere consecutive trebue ca raza minima sa fie 6, in primul caz segventa 20 24 26 nu este buna pentru ca distanta dintre 26 si 24 este 2, iar daca ne ducem cu 2 la stinga  nu intilnim nici un stilp.
SPOR