233 Hallway

[ditzone]

Aici puteţi discuta despre problema Hallway.

[•Marius]

Are cineva vreo idee cum se poate rezolva Hallway ? 

Ce complexitate are ideea ?

[•tm_radu]

Mie mi-au venit 2 idei pe masura ce o citeam:
1) cautare binara + verificare lee
2) o dinamica d[j] dimensiunea maxima pe care o poate avea bila pentru a putea ajunge in patratul ce are coltul stanga sus in coord de i si j...

n-am apucat sa le implementez 

[•tudalex]

Well varianta 1 cu cautare binara ia doar 70p ca iese din timp apoi. Fac cautarea de la 1000 in jos pana la 8 zecimale ceea ce face ca cautarea binara sa aiba maxim 40 de pasi so 40*1000^2 ar insemna o complexitate de 40.000.000 care iese din 0.1.

EDIT: Am reusit sa o fac sa ia 80p.