1102 Turnuri2

[•andrei.12]

Aici puteți discuta despre problema Turnuri2.

[•elfus]

Care este complexitatea optima de rezolvare? Multumesc anticipat.

[•devilkind]

Pentru 100 de puncte trebuie O(N).

[•dornescuvlad]

Are cineva un .in si un .ok cu o sursa de 100? Mersi 

[•Florian]

Mi-a mers de 100 destul de lejer cu N * logN. 

[•vladtarniceru]

pai nu cred ca e o(n) complexitatea avand in vedere ca limita e 1.7 sec nu ?

[•devilkind]

@Vlad Tarniceanu: Ba da. Am spus si mai sus, complexitatea optima este O(N).

Hint: Ca sa calculati primul turn din stanga/dreapta strict mai inalt folositi o stiva (e un algoritm destul de clasic). Acum ca sa determinati maximul pe intervalul vizibil din turnul incercati sa va folositi de elementele pe care turnul i le-a scos din stiva.

[•elfus]

Pentru O(N) e nevoie de un deque sau e doar o stiva obisnuita? La solutii e descrisa o alta metoda, fara a folosi nicio stiva (sau cel putin nu vad eu stiva) : http://infoarena.ro/algoritmiada-2011/runda-2/solutii/turnuri2

[•vladtarniceru]

eu am alta idee care nu e o(N)
fac cam asa:
iau un vector in care v[ i ] este pozitia turnului din stanga pana la care se poate vedea de pe turnul i
apoi fac un for de la 1 la n si det turnul pana la care se poate vedea asa:
daca sunt la turnul i, verific pentru turnul i - 1.
daca turnul i - 1 e mai inalt ca i atunci ne oprim si punem v[ i ] = i - 1;
daca nu ne ducem la v[i - 1], care e primul turn strict mai inalt ca i - 1 (sa zicem ca v[i - 1] = j) si verificam pentru ala
daca ala e mai inalt ne oprim si punem v[ i ] = j;
daca nu verificam pt v[j], care e primul turn strict mai inalt decat j
si tot asa...
asta pentru partea stanga, si pentru dreapta tot asa
si eu am pe un test cam o secunda, deci sigur nu e solutia buna, o sa ma uit la cea cu stiva chiar is curios cum ai scos o(n)
multumesc

L.E. : da mi se pare ca de fapt is aceleasi solutii nu?

[•DraStiK]

eu am alta idee care nu e o(N)
fac cam asa:
iau un vector in care v[ i ] este pozitia turnului din stanga pana la care se poate vedea de pe turnul i
apoi fac un for de la 1 la n si det turnul pana la care se poate vedea asa:
daca sunt la turnul i, verific pentru turnul i - 1.
daca turnul i - 1 e mai inalt ca i atunci ne oprim si punem v[ i ] = i - 1;
daca nu ne ducem la v[i - 1], care e primul turn strict mai inalt ca i - 1 (sa zicem ca v[i - 1] = j) si verificam pentru ala
daca ala e mai inalt ne oprim si punem v[ i ] = j;
daca nu verificam pt v[j], care e primul turn strict mai inalt decat j
si tot asa...
asta pentru partea stanga, si pentru dreapta tot asa
si eu am pe un test cam o secunda, deci sigur nu e solutia buna, o sa ma uit la cea cu stiva chiar is curios cum ai scos o(n)
multumesc

L.E. : da mi se pare ca de fapt is aceleasi solutii nu?

Da. Solutia cu stiva e aceasi cu solutia ta, care e defapt descrisa si in articolul cu solutii.

[•vladtarniceru]

da dar solutia nu e chiar O(n), e mai mult (O(n * nr de intoarceri) nu?)

[•SpiderMan]

Ti-am mai explicat, nr de intoarceri e PREA MIC si se ia O ( N ) .

[•devilkind]

Nu e din cauza ca numarul de intoarceri e prea mic. E din cauza ca fiecare numar va fi procesat o singura data. Algoritmul e echivalent cu urmatorul algoritm. Trec prin fiecare element in parte si il adaug intr-o stiva. Vreau sa mentin acea stiva sortata descrescator, astfel ca daca elementul din varful stivei e mai mic decat elementul pe care vreau sa il bag acuma incep sa scot din stiva pana cand in varful stivei ramane un element mai mare. In acest moment elementul din varful stivei este de altfel si primul element din stanga mai mare decat el (pentru dreapta faci la fel). De ce e acest lucru O(N). Simplu, pentru ca fiecare element intra in stiva o singura, si iese o singura data. E drept ca poate parea mai mult din cauza ca la fiecare pas trebuie sa mai si scoti niste elemente din stiva, insa gandestete ca suma numarului de elemente pe care le scoti e N.

[•nparfene2004]

Va rog sa-mi spuneti si mie care trebuie sa fie rezultatul corect pentru intrarea:
5
3 2
5 5
6 1
8 2
4 3
Multumesc

[•SpiderMan]

Cod:

5
5
5
5
3

[•darius96]

unpic mai simplu va rog.........nush foarte bun 

[•SpiderMan]

Nu exista mai simplu de atat, poti face un brute dar nu iei punctaj maxim.

[•Bit_Master]

Nu e din cauza ca numarul de intoarceri e prea mic. E din cauza ca fiecare numar va fi procesat o singura data. Algoritmul e echivalent cu urmatorul algoritm. Trec prin fiecare element in parte si il adaug intr-o stiva. Vreau sa mentin acea stiva sortata descrescator, astfel ca daca elementul din varful stivei e mai mic decat elementul pe care vreau sa il bag acuma incep sa scot din stiva pana cand in varful stivei ramane un element mai mare. In acest moment elementul din varful stivei este de altfel si primul element din stanga mai mare decat el (pentru dreapta faci la fel). De ce e acest lucru O(N). Simplu, pentru ca fiecare element intra in stiva o singura, si iese o singura data. E drept ca poate parea mai mult din cauza ca la fiecare pas trebuie sa mai si scoti niste elemente din stiva, insa gandestete ca suma numarului de elemente pe care le scoti e N.

Da, pentru ca tu atunci cand calculezi "zidul" (pana unde vede) pentru un anumit turn (turnul i), desi treci prin puncte intermediare pana ajungi la rezultat, nu vei mai trece din nou prin punctele intermediare pentru turnurile viitoare (de dupa i) pentru ca un turn viitor fie va "vedea" complet intervalul dintre zidul lui i si i, fie nu-l va vedea deloc (fiind blocat de turnul i). Deci tot acest interval dintre i si zidul sau va fi rezumat pe viitor doar consultand turnul i.

Fiecare turn va mai fi consultat o singura data (de zidul sau din partea opusa). Cand facem parcurgerea uitandu-ne spre stanga pt vizibilitate la turnul i, acest turn va fi dupa aceea "subordonat" zidului sau din dreapta k, i va fi folosit de catre k pt a i se calcula vizibilitatea si apoi nu va mai fi consultat i. Va fi consultat k cat si pentru i.

[•maritim]

Se mai pot obtine 100 pct cu solutia oficiala in acest moment?

Am incercat 2 variante, cu parsarea citirii si a afisarii (am afisat cu string) si tot ia doar 70 pct. Ce ar trebui sa fac?

[•dariusdarius]

Cred ca ar trebui marita limita de timp, sau adaugat la tag-uri "parsare", deoarece fara parsare nu intra in timp.

[•klamathix]

Am schimbat limita.

[•RadianEleven]

Imi poate spune cineva ce nu e corect? Ca nu gasesc