Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1102 Turnuri2  (Citit de 10084 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
andrei.12
Echipa infoarena
Nu mai tace
*****

Karma: 107
Deconectat Deconectat

Mesaje: 381



Vezi Profilul
« : Februarie 20, 2011, 20:33:44 »

Aici puteți discuta despre problema Turnuri2.
Memorat
elfus
Client obisnuit
**

Karma: 77
Deconectat Deconectat

Mesaje: 96



Vezi Profilul
« Răspunde #1 : Februarie 22, 2011, 19:50:17 »

Care este complexitatea optima de rezolvare? Multumesc anticipat.
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #2 : Februarie 22, 2011, 20:46:25 »

Pentru 100 de puncte trebuie O(N).
Memorat
dornescuvlad
Nu mai tace
*****

Karma: -138
Deconectat Deconectat

Mesaje: 234



Vezi Profilul
« Răspunde #3 : Februarie 23, 2011, 17:14:35 »

Are cineva un .in si un .ok cu o sursa de 100? Mersi  Smile
Memorat
Florian
Nu mai tace
*****

Karma: 125
Deconectat Deconectat

Mesaje: 832



Vezi Profilul
« Răspunde #4 : Februarie 24, 2011, 00:24:24 »

Mi-a mers de 100 destul de lejer cu N * logN.  Think
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #5 : Februarie 24, 2011, 17:46:17 »

pai nu cred ca e o(n) complexitatea avand in vedere ca limita e 1.7 sec nu ? Huh
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #6 : Februarie 24, 2011, 20:04:10 »

@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.
Memorat
elfus
Client obisnuit
**

Karma: 77
Deconectat Deconectat

Mesaje: 96



Vezi Profilul
« Răspunde #7 : Februarie 24, 2011, 20:42:28 »

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
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #8 : Februarie 24, 2011, 21:17:58 »

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) Smile
multumesc

L.E. : da mi se pare ca de fapt is aceleasi solutii nu? Very Happy
Memorat
DraStiK
Nu mai tace
*****

Karma: 131
Deconectat Deconectat

Mesaje: 207



Vezi Profilul
« Răspunde #9 : Februarie 25, 2011, 08:55:03 »

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) Smile
multumesc

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

Da. Solutia cu stiva e aceasi cu solutia ta, care e defapt descrisa si in articolul cu solutii.
Memorat
vladtarniceru
De-al casei
***

Karma: 81
Deconectat Deconectat

Mesaje: 145



Vezi Profilul
« Răspunde #10 : Februarie 25, 2011, 09:04:06 »

da dar solutia nu e chiar O(n), e mai mult (O(n * nr de intoarceri) nu?) Confused
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #11 : Februarie 25, 2011, 12:29:45 »

Ti-am mai explicat, nr de intoarceri e PREA MIC si se ia O ( N ) .
Memorat
devilkind
Echipa infoarena
Nu mai tace
*****

Karma: 284
Deconectat Deconectat

Mesaje: 1.240



Vezi Profilul
« Răspunde #12 : Februarie 25, 2011, 13:53:11 »

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.
Memorat
nparfene2004
Client obisnuit
**

Karma: 22
Deconectat Deconectat

Mesaje: 81



Vezi Profilul
« Răspunde #13 : Martie 05, 2011, 16:09:33 »

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
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #14 : Martie 05, 2011, 16:13:50 »

Cod:
5
5
5
5
3
Memorat
darius96
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #15 : Martie 08, 2011, 22:16:27 »

unpic mai simplu va rog.........nush foarte bun 
Memorat
SpiderMan
Nu mai tace
*****

Karma: -463
Deconectat Deconectat

Mesaje: 937



Vezi Profilul
« Răspunde #16 : Martie 09, 2011, 08:34:17 »

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

Karma: -49
Deconectat Deconectat

Mesaje: 159



Vezi Profilul
« Răspunde #17 : Martie 17, 2011, 13:35:37 »

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.
« Ultima modificare: Martie 17, 2011, 13:56:38 de către Alexandru-Iancu Caragicu » Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #18 : Noiembrie 12, 2011, 22:21:10 »

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?
Memorat
dariusdarius
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #19 : Iulie 01, 2013, 20:12:01 »

Cred ca ar trebui marita limita de timp, sau adaugat la tag-uri "parsare", deoarece fara parsare nu intra in timp.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #20 : Iulie 01, 2013, 20:36:19 »

Am schimbat limita.
Memorat
RadianEleven
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #21 : August 19, 2019, 14:26:41 »

Imi poate spune cineva ce nu e corect? Ca nu gasesc
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines