596 Caibicol

[•DITzoneC]

Aici puteţi discuta despre problema Caibicol.

[•Florian]

Ce complexitate ar trebui sa scot la pb asta? Am facut o dinamica cu 3 for-uri imbricate (aproximativ n^3) si iau 85 de puncte cu 3 tle-uri. Care e faza?

[•DITzoneC]

Ar trebui sa intre O(n³). Nu stiu ce sa zic, incearca sa mai optimizezi.

[•mihai0110]

am facut o dinamica cu n^2*k si iau 95 de p si un wa la testul 2, de ce nu stiu, mi se pare ca am rezolvat corect

LE nevermind, am luat 100, trebuia sa pun >= la un for in loc de >

[•Florian]

De fapt, complexitatea algoritmului meu e O(n*k*(n-k)). Nu imi intra in timp pe 3 teste... Si nu mi-a venit nici macar o idee de optimizare. Daca spui k intra O(n^3), de ce sa nu intre si programul meu? 

[•DITzoneC]

Ma rog prin O(n³) ma refeream la O(n²*k).

E drept ca este destul de stransa limita dar cu niste optimizari se poate obtine 100. Ai grija cum faci forurile(sa nu treci prin elemente inutile), cum faci accesarea elementelor matricii(uneori conteaza daca ai A[ i ][ j ] sau A[ j ][ i ], vezi articolul asta pontul 3) si alte detalii de-astea.

[•anna_bozianu]

Am si eu o intrebare. Am luat 100p pe problema asta dar recunosc ... am "furat" un test  . De ce oare sa nu imi mearga dinamica exact la un caz de genul nr_cai=nr_grajduri+1. E ceva special ceva care mie imi scapa ? Constituie un astfel de caz un caz special ? Si daca da ...  de ce ?

[•cos_min]

Am si eu o intrebare. Am luat 100p pe problema asta dar recunosc ... am "furat" un test  . De ce oare sa nu imi mearga dinamica exact la un caz de genul nr_cai=nr_grajduri+1. E ceva special ceva care mie imi scapa ? Constituie un astfel de caz un caz special ? Si daca da ...  de ce ?

Cum adica "nr_cai=nr_grajduri+1" ? Din enuntu reiese ca : nr_de_grajduri <= nr_cai ( K <= N ). Eu am luat 100 fara sa tratez vreun caz particular. 

[•anna_bozianu]

Simplu : n= k+1 ; k+1 > k => n > k . Oricum acesta e un caz banal in care raspunsul ori e 0 (cand exista macar doi cai de aceeasi culoare la rand ) ori e 1 ( cand sirul cailor e de tip 0 1 0 1 0 1 .... sau 1 0 1 0 1 0 ..... ) dar dintr-o greseala pe care eu nu reusesc sa o surprind nu obtin rezultatul corect. Intrucat obtineam 95 de puncte am presupus ca sunt in unul din cazurile

n=k ( cu raspuns 0 ) sau

k=1 ( cu raspuns nr_albi*nr_negri) sau

n=k+1 (cu raspuns 0 sau 1).

Asa am reusit sa prind si ultimul test.

[•manutruta]

Buna,

Am impresia ca nu se mai poate lua suta de cand s-a schimbat evaluatorul. Va rog verificati.

Toate cele bune,
Manu.

[•S7012MY]

Am zis si eu mai demult, dar nu s-a rezolvat. Totusi poti sa iei 100 daca parsezi si schimbi dimensiunile matricilor.

[•klamathix]

Am mărit limita.

[•CiboAndrei]

Sursa lui seamana cu a mea
Dar nu e neaparat sa fie stearsa, doar sa ii dati o atentionare