1. Noul (?) task filtering este mult imbunatatit, dar puteti pune un link pentru a ajunge acolo rapid? (Ex. in pagina Arhivei de probleme sau in meniul din stanga)
2. Nu stiu ce efort presupune, dar mi-ar placea sa pot scrie comentarii direct in pagina problemei (postarii, in cazul blogului), nu doar sa le citesc.

Solutia in N^5 avand constanta 4 merge in 1.2 implementata frumos.

Eu spun ca algoritmul meu e O(N^4) pentru ca parcurg matricea, si la fiecare pas, parcurg (in cel mai rau caz) toata matricea (unele elemente de 2-3-maxim 4 ori, dar nu cred ca asta inseamna N^5, doar o constanta). Nu imi dau seama de unde N^5: pentru fiecare element din matrice, ii parcurgi coloana, si pentru fiecare element de acolo, parcurgi intreaga matrice?

Pai asta e problema, cum gasesti care e cea mai lunga spirala care incepe cu el?

Daca intrebarea este "Este complexitatea N^4?", raspunsul e da, pentru fiecare element din matrice vizitez cel mult toata matricea (N^2 * N^2).
Daca intrebarea este "Cum ai implementat?": am doua functii, spirala_orar si spirala_trig, care incearca sa extinda spirala curenta cat mai mult tinand cont de punctul de plecare, parcursul de pana acum, si directia in care trebuie sa continui (sens trigonometric/orar). Si, nu, nu ma intorc in stari anterioare, informatiile necesare mi le transmit prin parametri. Am 40 de puncte cu TLE, deci nu memoria e problema.

Am regrupat testele si am marit limita de timp la Spirala3 ca sa intre solutiile in N^4 dar cu o constanta mai mare, iar cele in N^5 sa nu intre. Au fost reevaluate toate sursele.

O solutie N^4 nu ar fi si cea trecuta de mine in articolul de solutii, pentru fiecare element verific cea mai lunga spirala care incepe cu el? Inca are 40 de puncte...
In alta ordine de idei, poate cineva care a obtinut 100 de puncte la o problema sa dea idei de rezolvare in articolul de solutii?

Eu cred ca cele 2 seturi de instructiuni se pot executa fara ca cele 2 threaduri sa comunice, astfel incat, pe fiecare thread, variabila X, respectiv Y, ramane 0, urmand ca sincronizarea variabilelor globale sa se execute dua terminarea executarii celor 2 ramuri paralele.
In apararea eventualelor aberatii pe care le-am scris, pot spune ca nu stiu programare concurenta.

Frumos alese testele pe care avem feedback  

 Citat: "1. Numarul de interschimbari posibile este N² / 2".
Din enuntul problemei reiese altceva:
" deoarece avem 9 posibilitati de alegere a pozitiilor interschimbate, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), dintre care doar doua produc rezultatul dorit ((1, 2) si (2, 1)). " (n=3)
Cum e corect? Daca ar fi sa ne luam dupa articolul de solutii, pentru n impar nici nu e un numar intreg de posibilitati. Formula cred eu ca ar fi n*(n+1)/2, pentru fiecare prim element alegand al doilea element mai mare sau egal decat el (suma n+(n-1)+(n-2)+...+1). Totusi, am preferat sa nu modific, pentru ca nu sunt lamurit.

Am intalnit o situatie ciudata: iau 100 de puncte la problema Jocul, desi nu dau rapunsul corect pe exemplu. Sursa am trimis-o sa vad daca iau TLE si ar trebui sa gasesc o alta abordare (TLE+WA=probabl nu e buna ideea) si am vazut ca iau 100 de puncte. Eu abordez problema astfel: verific pentru fiecare numar cat e mult ma apropia de o valoare, fara sa o depasesc, adunandu-l cu valori calculate pentru numerele dinaintea lui. Intr-adevar, pe exemplu nu merge (da 46, nu 48), dar totusi a trecut de toate testele .

Am o problema: am implementat varianta cu 2 vectori de 300, si primesc 80 de puncte, un incorect si un KBS 11. Ar putea sa fie stack overflow? Declaratiile arata asa:

Cod:

int c[310],v[310],n,m,x,u;

, si mai am un i declarat local in main. Imi puteti sugera niste teste din care sa-mi pot da seama care e greseala?

Mie imi da tot asa: 4.285714. Mersi, oricum.
LE: Mi-a iesit de suta, o greseala stupida in cod

Eu si cu 2 zecimale, si cu 6 zecimale afisate, tot 75 iau. Imi poate cineva da un test propriu mai mare ca sa-mi dau seama ce caz nu prind? De mentionat ca nu am TLE, deci programul nu cicleaza.

Multumesc pentru toate lamuririle . Am reusit sa iau 100 

Am o problema: nu mai stiu cum exact transform un char in int, atunci cand charul memoreaza o cifra. Eu tineam minte ca trebuie sa scazi caracterul '48', adica '0'-'48'=0, '1'-'48'=1 etc, si intr-adevar cu aceasta implementare la mine afiseaza rezultatele corecte la toate testele pe care i le dau. Totusi, cand incarc sursa, evaluatorul ma anunta ca raspunsul e incorect. Nu e bun '48'-ul? Si daca nu, cum e corect?

Dar aici, ce pot sa fac? Am numa 4 puncte si ma dispera pt ca nu-i gasesc nici o hiba:(

Cod:

#include<fstream.h>
ifstream f("livada.in");
ofstream g("livada.out");
int v[250001];
char pomi[250001],t,t1;
int main()
{int nrp,n,m,i,j,maj,a,k,c,max,maxc;
long long p;
	nrp=i=j=k=c=max=maxc=0;
	f>>m>>n>>p;
	maj=n/2+1;
	for(i=1;i<=m;i++)
		{maxc=0;
		for(j=1;j<=n;j++)
			{f>>t;
			a=0;
			for(k=1;k<=nrp;k++)
				if(pomi[k]==t) {v[k]++;a=1;}
			if(a==0) {nrp++; pomi[nrp]=t; v[nrp]=1;}
			if(t==t1) maxc++;
				else {if(maxc>max) max=maxc;
						maxc=1;}
			t1=t;
			}
		t1='0';
		for(k=1;k<=nrp;k++) {if(v[k]>=maj) c++; v[k]=0;}
		nrp=0;}
	if(maxc>max) max=maxc;
	g<<c<<'\n'<<max<<'\n';
	f.close(); g.close();
	return 0;
}

Daca e nevoie,il scot dar chiar sunt curios unde nu merge.

Un KBS nu apare fara motiv niciodata. Vezi ca trebuie sa mai pui la sfarsit inca un test pt. max2. Si daca am priceput bine ce face secventa aia, ar trebui sa scoti if-ul din ea:

Cod:

 if(OK==0)
   { for(j=1;j<=n;j++)
	aux[x[j]]=0;
   }

Adi, vezi ca nu toata lumea stie chestiile alea pe biti pe care le sugerezi. Pentru cei care nu sunt la info intensiv, el sugereaza valoarea maxima care incape in tipul respectiv de variabile. Se mai poate initializa cu 2147483647 (valoarea maxima pe care o poate lua un int) sau cu INT_MAX din biblioteca limits.h:
http://en.wikipedia.org/wiki/Limits.h
Daca ai KBS 11 vezi exact cum merg pointerii (i-ul,j-ul si ce mai ai pe acolo) in vectori . Si nu stiu daca ai voie sa declari 2 vectori de 7 000 000 sau cat sunt acolo, si mai ales amandoi de int. Incearca sa-l faci pe unul de charuri si sa-i declari doar de 250001

Am si eu o observatie: nu cumva la:

Date de ieşire: fişierul numar.out va conţine:

ar trebui "numar4.out"? Ca bietul elev roman care a fost la OJI si a retinut titlul de acolo se poate incurca.(am luat 0 pct la primul upload pe fisier de iesire lipsa)

Mersi mult! Am luat suta:D:D:D

La problema asta se intampla ceva ciudat: am ok pe primele 3 teste si pe ultimul (care, judecand dupa memorie, e cel mai mare) si pe restul TLE. Cum pot sa ies din timp daca pe cel mai mare test imi intra, nu stiu. Am sortat structura cu mergesort si apoi am verificat cu :

Cod:

for(j=2;j<=n;j++)
		{q=1;
		while(q<j)
			if(a[q].s>a[j].s) {c++; q=j;}
				else q++;}

daca dispozitivul e redundant. Daca e un caz poate mai special va rog sa-mi dati un test sa ma prind si eu unde pica. Multumesc anticipat.

Am mai lasat problema cateva zile, acum m-am uitat iar pe ea si tot nu pricep ce gresesc. Pe testul postat de fireatmyself imi da bine. M-ar mai ajuta niste teste, sa vad si eu ce nu merge si sa corectez.
P.S. Nu-mi apare butonul "EDIT". O fi de la browser?

Am o problema: folosesc o formula, m-am uitat la raspunsuri si am vazut ca e aceeasi, dar iau WA pe toate testele.

In plus, daca folosesc <fstream> si using namespace std in loc de <fstream.h>, in calculatorul meu imi da 4 erori si nu ruleaza, dar pe infoarena ruleaza... tot WA...

Ma poate ajuta cineva si pe mine? Si niste teste m-ar ajuta. Multumesc anticipat!

100 in sfarsit:D:D:D ! Thx all pt sfaturi!

@klamathix: Afisez -1.
Caut binar un n care a indeplineasca conditia si numar zerourile cu puterile lui 5, am grija sa consider toate puterile pana in n. Nu cred ca am gresit pe undeva, pica pe mai mult de 1 test daca era asa. Cred ca e o chestie de finete, vreun caz particular... Ma gandeam ca poate cineva s-a mai lovit de asta si stie cum se rezolva.

Am 95 de puncte , doar WA pe testu 1  am grija de tot: afisez -1 cand trebuie, si iau chiar cel mai mic n care satisface conditia(asa reiesea din exemple), nush ce are ... Imi puteti da un indiciu de caz care poate mi-a scapat sau de o greseala in program? Chiar nu pricep ce are .

Mersi mult:)