664 Joctv

[•DITzoneC]

Aici puteţi discuta despre problema Joctv.

[•anna_bozianu]

Am trimis o sursa cu un algoritm de O(n^4) de 3 ori . Singura diferenta intre surse consta in introducerea unor comentarii. Rezultatele au fost :
 prima sursa ( fara comentarii ) => 80 puncte cu TLE pe testele 9 si 10
 a doua sursa ( + 2 linii comentarii) => 90 puncte cu TLE pe testul 8
 a treia sursa ( + 3 linii comentarii) => 70 puncte cu TLE pe testul 7, 8 si 10
Trebuie sa scriu un anume descantec in comentarii sau sa fac implementarea in O(n^3) pentru 100 p. Desigur am glumit ... dar totusi care e explicatia ? Se genereaza teste random sau sunt mereu aceleasi teste ?


Later edit :

A mers fara descantece cu implementarea de O(n^3)
 

[•devilkind]

pai e destul de simplu. Sursa e la limita. E normal ca o sursa care pe un test se incadreaza in timp la limita, a doua oara sa nu mai treaca, depinde in mare de cat de solicitat este procesorul in momentul in care iti este evaluata sursa, lucru care nu este intotdeauna  constant.

[•omu_salcam]

Si eu am luat TLE pe testul 7. Am trimis de 3 ori una dupa alta solutii, si mi-a dat 100 de pct

[•devilkind]

cu n^4??

[•Robytzza]

un point pt n^3 

[•wefgef]

Iti fixezi linia cea mai de sus si cea mai de jos a zonei dreptunghiulare alese si problema se reduce la determinarea subsecventei de suma maxima in O(N).

[•Robytzza]

  mam gandit asa da am zis ca nu merge  ,ms 

[•savim]

Incearca sa nu te complici, adica sa faci sursa cat mai simpla, si daca esti atent ar trebui sa iei o suta cu un timp de executie relativ mic...la mine max a fost 12ms, si sursa a avut 0.54kb.

[•anna_bozianu]

@Robytzza

Daca faci inainte de a incepe treaba

linia[ i ] = linia[ 1 ]+linia[ 2 ]+...linia[ i ]

folosind ideea simpla

linia [ i ]=linia [ i ]+linia[ i -1] pentru i=1..n ,

gandeste-te ce obtii in vectorul

 v=linia[ j ]-linia[ k-1 ] pentru 1<=j<=k<=n

si apoi ce inseamna

v [ x ] + v [ x+1 ] + ...+ v[ y ] pt x<=y 1<=x<=y<=n.

Cam pe aici se invarte ideea pt O(n^3).

[•Robytzza]

ms ana:D 

[•MciprianM]

 v=linia[ j ]-linia[ k-1 ] pentru 1<=j<=k<=n

si apoi ce inseamna

v [ x ] + v [ x+1 ] + ...+ v[ y ] pt x<=y 1<=x<=y<=n.

Nu inteleg de ce j<=k. Nu da v<0?
Si linia[1] inseamna suma elementelor de pe linia 1?
Cam pe aici se invarte ideea pt O(n^3).

[•Mishu91]

Pai iti faci sume partiale pentru fiecare coloana din matrice

Cod:

 for(int i=1; i<=n; i++)
     for(int j=1; j<=n; j++)
      S[i][j] = S[i-1][j] + A[i][j];

cva de genu arata codu. Si iti fixezi doua linii intre care vrei sa calculezi, iar de aici, avand precalculate sumele astea, iti ramane de aflat subsecventa de suma maxima dintr-un sir

[•crus]

am urmatoarea problema:
am trimis aceeasi suma, si pe
http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
si aici luam WA, iar pe infoarena am 100 de pct. ce problema poate sa fie?...adica...afisarea o faceam pe ecran, fara alte fisiere, e de la testele de pe infoarena?...sau de la site-u asta spaniol?

p.s. ma gandeam ca e de la siteu spaniol, pentru ca nu ma prind de afisare, daca se face standard sau nu, adica ca si la acm.timus.ru

[•MciprianM]

L.E. Am gasit greseala.

[•Bogdan_tmm]

Cod:

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			fscanf(f,"%ld",&a);
			s[i][j]=s[i-1][j]+a;
		}
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
		{
			s1=sm=0;
			for(i1=1;i1<=n;i1++)
			{
                          aux=s[j][i1]-s[i-1][i1];
                          (de aici in jos sigur e bine)
                          ..................
                        }
                }

iau 50 p in o(4*n) si in o(3*n)-sursa asta si culmea cad aceleasi teste :|Oare dc?(
la: kiar unde zisei ca e bine nu era corect =)))))))))

[•MihaiG]

salut, cred ca ar trebuii modificat enuntu sau scrieti la restrictii pentru ca se cere un dreptunghi, iar eu am luat considerat prima data a extremitatea de jos a dreptunghiului ia val de la i+1 la n(ca sa nu mai spun numaram si coloanele pentru ca numarul acestora sa fie >=2 pentru ca solutia sa fie valida) si am luat 80. dupa ce am modificat i+1 cu i am scos tot ce era cu variabila ce memora numarul coloanelor am luat 100... inseamna ca pe 2 teste nu sunt dreptunghiuri ci sunt linii.
la oli au "gresit" cativa asa?
va pup

[•wefgef]

De unde ai tras tu concluzia ca "o zona dreptunghiulara" trebuie sa fie o submatrice cu cel putin 2 coloane/linii?

[•mihai995]

ar trebui marite putin limitele pentru N sau scrimbate testele... nu sunt suficient de bune si data o reevaluare... am luat 100p cu N^4

[•S7012MY]

Testele la problema asta nu sunt foarte bune. Se poate lua 100 cu o sursa care nu testeaza daca dreptunghiul de suma maxima e un element de pe prima coloana.

[•informatician28]

Iau incorect la testul 5 . Ce ar putea fi? 
Verific inclusiv daca am solutie doar pe prima linie...

[•mihaimusat]

Ce e  asa special la ultimul test ? Sursa mea aici : http://www.infoarena.ro/job_detail/1415518

[•hasmasandragos]

Concurentul poate sa aleaga o zona nula (adica sa nu aleaga nimic) daca nu exista vreo zona care sa ii aduca profit.