Morcovi

[•wefgef]

Aici se pot pune intrebari legate de problema Morcovi de la Runda Finala a concursului Algoritmiada 2009.

Timpul alocat intrebarilor este de 1 ora. Intrebarile vor fi formulate astfel incat sa se poate raspunda cu DA sau NU. In caz contrar sau in cazul in care intrebarea isi gaseste raspuns in enuntul problemei, raspunsul va fi FARA COMENTARII.

[•wefgef]

Timpul alocat intrebarilor e expirat. Multa bafta in continuare!

[•gabitzish1]

Buru de ce nu ne da feedback la evaluare? 

[•runnaway90]

poate sa nu execute toate salturile si sa fie maxim ? sau trebuie toate neaparat.

 si stie ca acesta executa toate aceste salturi intr-o ordine oarecare.

[•gh09]

Cei care ati luat 100 la morcovi ce compl aveti ?

[•anna_bozianu]

n * (2^p)

[•gh09]

defapt e N * (2 ^ P) * P - si iau TLE pe 2 teste (


Imi poate spune si mie dc daca declar asa o matrice D[4100][1010] merge mult mai rapid decat D[1010][4100] ?  Am stat o ora la problema asta ca imi iesea din timp pe 2 teste din cauza asta....

[editat] nu mai posta consecutiv

[•sima_cotizo]

Cel mai probabil spargeai cache-ul des

[•gh09]

Parca cache-ul se spargea daca puneai dimensiunea mai mare ca linie.....si nu invers!

[•devilkind]

Nu. Atunci cand accesezi un element procesorul incarca in cache toata linia din matrice. Tu daca faceai A[1001][4100] inseamna ca parcurgeai matricea intai pe coloane si apoi linii si astfel pentru fiecare element tu inserai o linie noua in cache. Sper ca ai inteles asa intuitiv ce vreau sa zic. In principiu e mai bine sa mergi intai pe linii si apoi pe coloane decat invers.

[•anna_bozianu]

Eu am declarat matricea fix 4096x1000 si am indexat din 0.
Complexitatea este intradevar n*(2^p)*p.
Chiar am sa incerc de curiozitate sa modific sursa. In forma asta cel mai mare timp de executie la mine e de 300 ms. Revin cu un L.E. dupa ce incerc.

L.E.  Intradevar efectul este devastator. Aceeasi sursa dar schimband liniile cu coloanele imi da 50 de puncte iar restul testelor sunt T.L.E.
        Cu ocazia asta am mai invatat ceva.

[•sima_cotizo]

L.E.  Intradevar efectul este devastator. Aceeasi sursa dar schimband liniile cu coloanele imi da 50 de puncte iar restul testelor sunt T.L.E.

Same here stiu cum e...

[•chera_lary]

Unde poate fi gasita solutia la aceasta problema?

[•marcelcodrea]

Poti sa gasesti solutia la problema Morcovi aici.