•Cosmin
|
|
« : Aprilie 11, 2006, 14:35:10 » |
|
Aici puteţi discuta despre problema Order.
|
|
|
Memorat
|
|
|
|
alex_g
Vizitator
|
|
« Răspunde #1 : 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 .
|
|
|
Memorat
|
|
|
|
•alexthero
|
|
« Răspunde #2 : 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
|
|
|
Memorat
|
Tine minte ca mintea conduce pumnu, nu invers
|
|
|
•pauldb
|
|
« Răspunde #3 : 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.
|
|
|
Memorat
|
Am zis
|
|
|
•devilkind
|
|
« Răspunde #4 : 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)
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #5 : 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 .
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #6 : August 24, 2006, 15:44:21 » |
|
nu sunt taraneli sunt optimizari
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #7 : August 24, 2006, 23:14:43 » |
|
Sunt algoritmi cu o complexitate mai mare, deci taraneli.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
vladut.forum
Vizitator
|
|
« Răspunde #8 : 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)
|
|
|
Memorat
|
|
|
|
•greco
|
|
« Răspunde #9 : August 25, 2006, 13:37:49 » |
|
Nu... alea sunt bulaneli. E o diferenta.
|
|
|
Memorat
|
Jump in the cockpit and start up the engines Remove all the wheelblocks there's no time to waste Gathering speed as we head down the runway Gotta get airborne before it's too late.
|
|
|
•tm_radu
|
|
« Răspunde #10 : Septembrie 28, 2006, 20:09:04 » |
|
Eu am scos O(n) si totusi iau TLE pe ultimele 2 teste
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
ditzone
Vizitator
|
|
« Răspunde #11 : 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)
|
|
|
Memorat
|
|
|
|
•tm_radu
|
|
« Răspunde #12 : Septembrie 28, 2006, 20:39:10 » |
|
aham ...si in O(n * log n) cum s-ar rezolva?
|
|
|
Memorat
|
Daca nu merge o preblema, depaneaz-o, si abia apoi arunci calculatoru pe geam
|
|
|
ditzone
Vizitator
|
|
« Răspunde #13 : 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..
|
|
|
Memorat
|
|
|
|
|