1095 Knumere

[•wefgef]

Aici puteti discuta despre problema Knumere.

[•spatarel]

Am participat la concurs on-site si, apoi, am ascultat solutiile oficiale. Propun o solutie alternativa, cu care am obtinut punctaj maxim:

Se cauta binar solutia. In acest sens, trebuie implementata o functie prin care sa se verifice daca pentru un numar D, exista o subsecventa a sirului de intrare de lungime cel putin N - K, in care oricare doua elemente consecutive au diferenta <= D.

Astept pareri despre corectitudine, timpul de executie si dificultatea de implementare.

[•Florian]

Banuiesc ca aceasta solutie nu ar trebui sa intre in timp. Pentru ca se poate si mai bine de O(NlogN). 

[•spatarel]

Solutia are o complexitate teoretica chiar mai proasta: O(N log D), unde D = 2*10^9, diferenta maxima dintre doua numere consecutive. Si totusi... Testul 10 - 640ms. Timpii de executie depind, in cazuri atat de fine, de complexitatea structurilor de date folosite si calitatea implementarii.

[•vendetta]

Am implementat solutia lui spatarel dar  i`au  90 de pct cu wa pe testul 2... Ma poate ajuta careva ?

[•eudanip]

Pai se poate cu o complexitate mai buna.

 Hint : deque  

[•CosminRusu]

Buna.
Iau 90 de puncte cu WA pe primul test. Imi puteti da un exemplu asemanator cu acesta? Am implementat ideea cu deque-uri. Multumesc anticipat.

[•AlexandruValeanu]

Salut!
In caz ca te mai intereseaza gresesti cand scoti un element din deque( cand nu mai poate face parte din secventa ). Secventa fiind de lungime L-1 nu trebuie scos atunci cand
 

Cod:

if( i - dq.front() >= l )
            dq.pop_front();

ci atunci cand

Cod:

if( i - dq.front() >= l - 1 )
            dq.pop_front();

.

Cu aceasta modificare sursa de ia 100p. Bafta!

PS: Dupa parerea mea ar trebui sa modifici si in while deoarece nu are rost sa tin un element in deque daca cel pe care urmeaza sa il inserez este egal cu el.
Ma refer la

Cod:

v[ dq.back() ] < v[i]

care ar trebui sa fie

Cod:

v[ dq.back() ] <= v[i]