|
Titlul: 238 Order Scris de: Cosmin Negruseri din Aprilie 11, 2006, 14:35:10 Aici puteţi discuta despre problema Order (http://infoarena.ro/problema/order).
Titlul: Raspuns: 238 Order Scris de: alex_g din Aprilie 12, 2006, 11:20:34 Sigur exemplul este bun? Mie mi se pare ca dupa primii trei pasi se elimina copii 2 4 1 si atunci ne aflam pe
pozitia 1 , dupa care incepem sa numaram 4 pozitii incepand de pe pozitia 2 deci urmeaza 2 3 4 5 !!!! Ceea ce ar insemna ca al 4-lea copil eliminat sa fie 5 nu 3 cum scrie in exemplu. Poate ma lamureste si pe mine cineva.....sau poate nu am numarat bine :?. Titlul: Raspuns: 238 Order Scris de: Tandrau Alexandru din Aprilie 12, 2006, 11:32:16 Nu se mai numara copiii care au fost eliminati
1: 1 2 3 4 5 6 - se elimina 2 2: 1 3 4 5 6 - se elimina 4 3: 1 3 5 6 - se elimina 1 4: 3 5 6 - se elimina 3 5: 5 6 - se elimina 5 6: 6 - se elimina 6 Titlul: Raspuns: 238 Order Scris de: Paul-Dan Baltescu din August 24, 2006, 15:09:24 Poate cineva sa-mi dea niste indicii cum se rezolva problema? :'(
Eu iau 65 de puncte (restul TLE) si am o rezolvare in O(N^2*). Desi este evident ca asa o complexitate nu are cum sa intre in timp este supraapreciata. Oricum...e cea mai buna idee pe care am avut-o. :sad: Titlul: Raspuns: 238 Order Scris de: Savin Tiberiu din August 24, 2006, 15:29:33 poti sa o mai reduci observand ca la pe la ultimele elemente tu parcurgi siru de 5 ori si ajungi la urmatoru element, incearca sa elimini aceste parcurgeri inutile. cu observatia asta iei 90. banuiesc ca solutia oficiala include skiplisturi (banuiesc)
Titlul: Raspuns: 238 Order Scris de: Cosmin Negruseri din August 24, 2006, 15:40:04 Merge in O(n log n) cu arbori de intervale. Voi schimba testele ca sa se ia mai putin de 90 cu tzaraneli :).
Titlul: Raspuns: 238 Order Scris de: Savin Tiberiu din August 24, 2006, 15:44:21 nu sunt taraneli sunt optimizari :D
Titlul: Re: 238 Order Scris de: Tiberiu-Lucian Florea din August 24, 2006, 23:14:43 Sunt algoritmi cu o complexitate mai mare, deci taraneli.
Titlul: Raspuns: 238 Order Scris de: vladut.forum din August 25, 2006, 08:03:29 yeheh,, eu consider orice greedy aproape nedemonstrat (nici macar intuitiv).. tzaraneala.. si asta poate sa aiba complexitatea <= decat algoritmul oficial ;) (am zis paote)
;) Titlul: Raspuns: 238 Order Scris de: Tiberiu-Lucian Florea din August 25, 2006, 13:37:49 Nu... alea sunt bulaneli. E o diferenta. 8)
Titlul: Raspuns: 238 Order Scris de: Toma Radu din Septembrie 28, 2006, 20:09:04 Eu am scos O(n) si totusi iau TLE pe ultimele 2 teste :-k
Titlul: Raspuns: 238 Order Scris de: ditzone din Septembrie 28, 2006, 20:34:58 Ce faci tu nu este O(n), operatia erase aplicata unui vector nu este O(1)... ( sau operatia de incrementare a unui pointer)
Titlul: Raspuns: 238 Order Scris de: Toma Radu din Septembrie 28, 2006, 20:39:10 aham :-k ...si in O(n * log n) cum s-ar rezolva?
Titlul: Raspuns: 238 Order Scris de: ditzone din Septembrie 28, 2006, 20:40:16 cum s-a spus si mai sus .. folosind arbori de intervale, skiplist.. ce vrei tu, deasemenea se poate rezolva si in O(n* sqrt(n) ) daca nu ma insel..
|