|
Titlul: 1046 Stalpisori Scris de: Paul-Dan Baltescu din Mai 10, 2010, 08:01:13 Aici puteti discuta despre problema Stalpisori (http://infoarena.ro/problema/stalpisori).
Titlul: Răspuns: 1046 Stalpisori Scris de: Dragos din August 28, 2010, 16:05:53 Imi da si mie cineva un hint pentru solutia de 100?
Pana acum am facut n*log P[n]* log n. Multumesc anticipat! Titlul: Răspuns: 1046 Stalpisori Scris de: Mircea Dima din August 28, 2010, 16:30:18 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 :)
Titlul: Răspuns: 1046 Stalpisori Scris de: Dragos din August 28, 2010, 18:06:23 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 :wink: Titlul: Răspuns: 1046 Stalpisori Scris de: Stefan Eniceicu din Aprilie 15, 2012, 13:45:04 Solutia optima e O(N), nu mai merge O(N * log (P[N - 1])) oricate optimizari ai face, hope it helps.
Titlul: Răspuns: 1046 Stalpisori Scris de: Salajan Razvan din Octombrie 28, 2012, 11:57:14 Salut! Am rezolvare in O(log P[n] * n) si iau 70 de puncte. Ceva indicii pentru o complexitate mai buna ?
Titlul: Răspuns: 1046 Stalpisori Scris de: UAIC.VlasCatalin din Noiembrie 01, 2012, 20:08:31 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 :) |