019 Pavare

[•pauldb]

Testele nu au fost schimbate. Si tin minte ca am rezolvat problema cu o solutie avand complexitatea O(N*M*2^2M) (supraestimat).

Cred ca mai mult ca sigur o solutie avand complexitatea O(N*M*2^M) s-ar incadra in timp. Esti sigur insa ca asta e complexitatea solutiei tale?

[•dushmi]

Sunt destul de sigur.. adica am dinamica a[ i ][ j ][ k ] = pozitia i,j cu configuratia k ( 0 <= k <= (2^m - 1) ). Si pentru fiecare triplet (i, j, k) vad in o(1) in ce alte triplete  pot sa ma duc( sunt maxim 2 triplete in care pot ajunge).

[•geniucos]

Mie imi da bine pe mabele teste postate inainte dar tot iau 0 imi mai poate propune cineva niste teste.Multumesc anticipat.

[•geniucos]

Nu imi mai trebuie am luat 100 nu am luat in calcul ca pot sa existe linii intregi pe care nu poti sa pui nici un bloc
de ex

****
****
|*|*
*|*|
****
****
cu | am marcat zona stricata

[•assa98]

Un test micut imi puteti da si mie, va rog?

[•lvamanu]

Am intampinat o problema la evaluare. Cand trimit problema primesc pe borderou urmatorul mesaj:
Contactează autorul problemei: Evaluatorul nu a returnat un număr la stdout pe testul 1 (se ignoră spaţii, newline, etc)

Poate fi din cauza sursei mele sau este o problema cu testele?

[•Maarcell]

Ar trebuie o solutie in O(4^M*N) sa mearga? Eu am facut o dinamica cu back pe fiecare linie, si tineam starea liniei anterioare. Ce-i drept, am facut-o intr-un mod mai "destept", facand dinamica "inainte", un fel de parcurgere BFS. A trecut cu 24 de ms pe ultimul test, cu mult mai repede decat solutiile in O(2^N*N*M). Totusi ma intreb care e logica solutiei oficiale optime?

Edit: Dupa o analiza mai atenta, am observat ca complexitatea algoritmului e mai apropiata de O(2^M*fib(M)*N).

[•SebiSebi]

Ar merge marita putin limita de timp. O solutie cu O(2^M * N * M) ia TLE daca nu e optimizata.