238 Order

[•Cosmin]

Aici puteţi discuta despre problema Order.

[alex_g]

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  .

[•alexthero]

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

[•pauldb]

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. 

[•devilkind]

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)

[•Cosmin]

Merge in O(n log n) cu arbori de intervale. Voi schimba testele ca sa se ia mai putin de 90 cu tzaraneli .

[•devilkind]

nu sunt taraneli sunt optimizari

[•greco]

Sunt algoritmi cu o complexitate mai mare, deci taraneli.

[vladut.forum]

yeheh,, eu consider orice greedy aproape nedemonstrat (nici macar intuitiv).. tzaraneala.. si asta poate sa aiba complexitatea <= decat algoritmul oficial (am zis paote)

[•greco]

Nu... alea sunt bulaneli. E o diferenta. 

[•tm_radu]

Eu am scos O(n) si totusi iau TLE pe ultimele 2 teste 

[ditzone]

Ce faci tu nu este O(n), operatia erase aplicata unui vector nu este O(1)... ( sau operatia de incrementare a unui pointer)

[•tm_radu]

aham ...si in O(n * log n) cum s-ar rezolva?

[ditzone]

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..