|
Titlul: 596 Caibicol Scris de: Adrian Diaconu din Noiembrie 09, 2007, 16:07:32 Aici puteţi discuta despre problema Caibicol (http://infoarena.ro/problema/caibicol).
Titlul: Răspuns: 596 Caibicol Scris de: Florian Marcu din Noiembrie 18, 2007, 13:48:03 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?
Titlul: Răspuns: 596 Caibicol Scris de: Adrian Diaconu din Noiembrie 18, 2007, 14:39:41 Ar trebui sa intre O(n3). Nu stiu ce sa zic, incearca sa mai optimizezi.
Titlul: Răspuns: 596 Caibicol Scris de: Bivol Mihai din Noiembrie 19, 2007, 17:30:28 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 > Titlul: Răspuns: 596 Caibicol Scris de: Florian Marcu din Noiembrie 21, 2007, 17:45:41 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? ???
Titlul: Răspuns: 596 Caibicol Scris de: Adrian Diaconu din Noiembrie 21, 2007, 21:55:00 Ma rog prin O(n3) ma refeream la O(n2*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 (http://infoarena.ro/12-ponturi-pentru-programatorii-CC) pontul 3) si alte detalii de-astea. Titlul: Răspuns: 596 Caibicol Scris de: Bozianu Ana din Noiembrie 22, 2007, 19:58:31 Am si eu o intrebare. Am luat 100p pe problema asta dar recunosc ... am "furat" un test :oops: . 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 ?
Titlul: Răspuns: 596 Caibicol Scris de: Bondane Cosmin din Noiembrie 22, 2007, 21:58:31 Am si eu o intrebare. Am luat 100p pe problema asta dar recunosc ... am "furat" un test :oops: . 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. :wink: Titlul: Răspuns: 596 Caibicol Scris de: Bozianu Ana din Noiembrie 23, 2007, 07:38:43 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. Titlul: Răspuns: 596 Caibicol Scris de: Emanuel Truta din Ianuarie 17, 2014, 00:20:10 Buna,
Am impresia ca nu se mai poate lua suta de cand s-a schimbat evaluatorul. Va rog verificati. Toate cele bune, Manu. Titlul: Răspuns: 596 Caibicol Scris de: Petru Trimbitas din Ianuarie 17, 2014, 00:31:58 Am zis si eu mai demult, dar nu s-a rezolvat. Totusi poti sa iei 100 daca parsezi si schimbi dimensiunile matricilor.
Titlul: Răspuns: 596 Caibicol Scris de: Mihai Calancea din Ianuarie 17, 2014, 02:21:52 Am mărit limita.
Titlul: Răspuns: 596 Caibicol Scris de: Andrei Cibo din Octombrie 28, 2017, 14:58:35 Sursa lui seamana cu a mea
Dar nu e neaparat sa fie stearsa, doar sa ii dati o atentionare :wink: |