1121 Carti2

[•andrei.12]

Aici puteti discuta despre problema Carti2.

[•AndrewTheGreat]

E posibil sa pun o carte peste alta carte fara a folosi raft? Spre ex: am pe raft o carte cu H = 5 si L = 1 si una cu H = 3 si L = 1 pot sa adaug peste a 2a carte o alta carte H = 2 si L = 1?

[•stocarul]

E posibil sa pun o carte peste alta carte fara a folosi raft? Spre ex: am pe raft o carte cu H = 5 si L = 1 si una cu H = 3 si L = 1 pot sa adaug peste a 2a carte o alta carte H = 2 si L = 1?

Nu.

[•Andreid91]

Ce complexitate are solutia oficiala  ?   Vad ca cea de O(n*3^n) merge pe 50 pct...

[•DraStiK]

Ce complexitate are solutia oficiala  ?   Vad ca cea de O(n*3^n) merge pe 50 pct...

Poți scăpa de un N și atunci o sa ai O (3^N).

[•Andreid91]

Poți scăpa de un N și atunci o sa ai O (3^N).

Imi scapa ideea ta...Pana la urma am facut niste preprocesari in n*(3^n) si  fiecare test il rezolv in n*(2^n)+3^n . Naspa e ca folosesc foarte multa memorie , vreo 5 vectori de 3^n.  Vreun hint ceva tu cum ai scapat de atata memorie ??  

   

[•DraStiK]

Poți scăpa de un N și atunci o sa ai O (3^N).

Imi scapa ideea ta...Pana la urma am facut niste preprocesari in n*(3^n) si  fiecare test il rezolv in n*(2^n)+3^n . Naspa e ca folosesc foarte multa memorie , vreo 5 vectori de 3^n.  Vreun hint ceva tu cum ai scapat de atata memorie ??  

Si eu am preprocesat în O (N*2^N) un vector H[stare] - înălțimea maxima a unei cărți din configurația stării, dacă configurația stării încape pe un raft.

Si apoi rezolvi dinamica în O (3^N). Cred ca rezolvarea noastră e la fel, și nu m-am exprimat eu prea bine

[•repp4radu]

Salut!

Am vazut ca mai multe persoane care luau 95p cu WA pe testul 2 au ajuns la 100. Imi puteti spune si mie ce are deosebit acest test? 

[•alex_ovidiunitu]

Pentru cei care pica testul 2: ganditi-va si la cazul cand in biblioteca nu poate intra nici o carte.