Clasamentul trebuie sa fie vizibil pe perioada concursului?

Pff,exact acum v-ati gasit sa ascundeti punctajele. Nu mi se pare ok ce s-a intamplat,adica ori e un concurs cu punctaje vizibile ori nu.Timp de aproape 3 ore multe concurente au putut vedea punctajele la probleme si astfel si-au mai putut depana sursa sa scoata 100.Daca tot le-ati oferit la o parte acest avantaj macar lasati la toate si faceti punctajele vizibile din nou.  Sau macar sa fie ca al Algoritmiada si testele vizibile sa fie unul din primele 3 si unul din ultimele 3,adica un test mic si unul mare,nu primele 2 teste.

Cod:

D[i] += (t = (D[i] -= ((i <= B[0]) ? B[i] : 0) + t) < 0) * 10;

is pretty evil... Never change the same variable twice in the same statement. Comportamentul este nedefinit, si in functie de compilatorul pe care il folosesti, s-ar putea sa mearga, s-ar putea sa nu.

Nu te stradui sa faci codul prea smecher. Eu am invatat lectia asta in prima mea runda la campion, cand am luat 0 dintr-o smecherie similara.

OK.
Am modificat acel rand si intr-adevar acum ia 100. Mersi de sfat 

@scipianus: Referitor la sursele de la munte3
#615470 e eroare de compilare in sursa ta, nu in evaluator. Probabil nu ai inclus headerul corect pentru functia memset. Schimbarea este datorata versiunii mai noi a compilatorului

#615475 nu da raspuns corect pe calculatorul meu.

La prima da,am modificat si am facut memset manual (sincer nu stiu care este biblioteca pentru memset).Dar a doua modificata cu memset "manual" am trimis-o si pe aceea pe campion si ia 100  De ce ?

<cstring>. campion-ul are alt eval, nu te poti astepta la aceleasi rezultate

1.Mersi de informatia despre memset
2."nu te poti astepta la aceleasi rezultate" inseamna la tine 0pct fata de 100?  Eu nu vad nimic ambiguu in sursa mea,am modificat-o acum iarasi cu cstring si memset,am mai pus pe-acolo niste short si alte chestii,am examinat-o si nu vad nimic  Am trimis acum pe campion : 100 ,pe infoarena : 0 (WA pe toate) 

@scipianus: Referitor la sursele de la munte3
#615470 e eroare de compilare in sursa ta, nu in evaluator. Probabil nu ai inclus headerul corect pentru functia memset. Schimbarea este datorata versiunii mai noi a compilatorului

#615475 nu da raspuns corect pe calculatorul meu.

La prima da,am modificat si am facut memset manual (sincer nu stiu care este biblioteca pentru memset).Dar a doua modificata cu memset "manual" am trimis-o si pe aceea pe campion si ia 100  De ce ?

Se mai uita cineva din moderatori pe http://infoarena.ro/calibrare-limite-de-timp pentru a incerca sa rezolve problemele aparute? 

Presupun ca da,ca doar la urma urmei e un concurs online cu rating (deci e bun de antrenament si pentru rating,caci n-a mai fost de ceva vreme unul),iar in regulament nu scrie despre cine s-ar putea inscrie,zice doar ca se vor califica primele 30 fete,deci baietii ar avea voie sa participe,dar nu se pot califica pentru tabara  Inscrie-te si tu Alex 

Daca iau WA (http://infoarena.ro/job_detail/615498) nu poate fi din vina evaluatorului nou,nu? Care vreti sa ma ajutati sa-mi ziceti sa va dau prin PM sursa sa vedeti daca e ceva in neregula,desi nu inteleg,ca doar e o dinamica banala 

Ok, ONI e la Iasi, dar cand este??!?!?

Din cate am inteles anul asta nationalele de mate,info,etc. (care mai erau in vacanta de Paste) vor fi cu o saptamana inainte de vacanta de Paste(care anul asta este de 2 saptamani). Si fiind de-acum in timpul anului scolar,inseamna ca vor lipsi profesorii care sunt in comisii nationale asa ca ministerul a bagat saptamana respectiva programul "Scoala altfel" (despre care ati aflat ce e,presupun) 

Da,in sfarsit cineva care a strans tot ce este bun din comentariile anterioare  Probabil o prima solutie ce s-ar putea aplica fara mari probleme ar fi urmatoarea :

4. Domnul profesor Radu Gramatovici a propus o solutie foarte interesanta. Limita de 40 pct. pentru calificarea la ONI pentru a evita calificarea cu 2 pct in detrimentul unor elevi cu 100-150 de puncte.

Ideea aceasta ar fi si una normala,intrucat la alte olimpiade,gen matematica,ea exista 
Ideea cu K elevi de liceu n-are nici o parte benefica,pur si simplu distruge ICHB-ul + restul centrelor tari (Vianu,Ploiesti,Iasi,Craiova) si in final distruge si loturile Romaniei. 
Cat despre partea cu atragerea elevilor catre informatica,aici probabil si profesorii din tara ar trebui sa-si dea mai mult interesul la predare (nu vorbesc despre profesorii buni,ci in general despre restul pentru care informatica parca n-ar fi materia lor),sa atraga elevii la concursurii,sa-i directioneze catre Infoarena si Campion(de unde mai departe vor lucra si invata si singuri dezvoltand probabil in final o pasiune pentru informatica),unde eventual ar putea fi puse asa cum zicea Mircea Pasoi si video-uri cu lectii de informatica de performanta filmate de studenti/profesori (gen cum exista pe internet acele filmari de la cursurile MIT , asa s-ar putea face si de catre cei de la ICHB daca s-ar dori asa ceva  ).

Nu siu daca este buna ideea cu "maxim 4 pe liceu".  Pot sa dau un exemplu foarte simplu: Sa luam la intamplare doua judete X si Y. Exista multe situatii cand un elev din judetul X ia 70 de puncte la OJI (e primul pe judet si merge la ONI) iar un alt elev din judetul Y ia 120 de puncte dar nu are nicio sansa de ONI (pentru ca exista scoruri mai mari la clasa lui pe judet). Si atunci defapt la nationala nu se mai triaza cei mai buni...

Da,de acord. Pe www.olimpiada.info se face in fiecare an un clasament national pentru OJI si acolo se vede ca multi care au punctaje mari,de peste 100-130pct nu se califica in judetele tari (gen Bucuresti,unde desi sunt 31 locuri,totusi ICHB si Vianu ar putea da mai mult de atat) , iar in judetele slabe cu 3-4 locuri se califica punctaje de tot rasul.Nu zic la mine in judet unde ultimii 2 calificati au avut putin peste 60,dar de exemplu in Mehedinti parca s-a intrat pe principiul "care nu ia 0 se califica" de au intrat cu 10-20 pct pe cele 3 locuri  . Ce pretentii sa ai de la respectivii la ONI? Normal ca ocupa niste locuri pe care le-ar fi putut ocupa cei cu punctaje de peste 100 necalificati.

Nu cred ca sistemul de 4 pe liceu ar fi ceva prea bun pentru ca astfel ar fugi toti de la ICHB in licee anonime ca sa se poata califica   . Dar iarasi zic,un sistem cu OJI de 2 probleme e prea putin,adica probabil ar fi mult mai bine sa fie un sistem de calificare care incepe inca de prin octombrie-noiembrie cu runde de calificare ,in genul celui de la Campion , iar la final la fel un clasament total pe clase din care sa se califice primii X elevi   . (mai putini decat se califica acum pe la a 9-a sau a 10-a ,pentru ca e prea mult sa fie 80 participanti,cand vreun sfert sau mai mult au venit cu punctaje de pana in 50 pct)

Nu cred ca se stie sigur inca. Se zvonea ca la Iasi : mai ales ca la Urmasii lui Moisil s-a zis ca liceul Moisil Iasi isi propune sa obtina gazduirea ONI 2012 

de ce numele fisierelor de intrare/iesire sunt "expresie2" in loc de "expresie3" ?   

Da,de aceeasi parere sunt si eu. Avand formula pentru al n-lea termen trebuie facuta doar ridicarea la putere in timp logaritmic,deci complexitate O(log n) , doar ca precizia nu stiu cat de mare va fi la radicalii aia  .

Pai asta e o problema clasica de dinamica.
Am nota prada[ i ] = prada maxima pe care ar lua-o hotul daca jefuieste "optim" in intervalul caselor 1...i,jefuind obligatoriu casa i
Deci prada [ i ] = A[ i ] + max(prada[i-2],prada[i-3]) , cu initializarile prada[0]=0, prada[1]=A[1], prada[2]=A[2] , eventual si prada[3]=A[3]+A[1] , iar recurenta o rulezi pentru i=4,n sau i=3,n

N-am inteles asta cu "jefuieste optim" dar si "jefuind obligatoriu casa i". Eu cred ca nu-ti da bine pe teste de genul asta:

Cod:

5 1 5 1 1 5 1 5

Deci prada[ i ] = prada maxima pe care o poate capata hotul jefuind case in intervalul 1....i ,casa i fiind obligatoriu jefuita.
Am uitat sa precizez ca solutia va fi max(prada[n],prada[n-1]).
Pe exemplul tau vectorul prada va fi :
0 5 1 10 6 11 15 12 20 iar solutia este max(12,20) = 20. 

Explicatia recurentei este ca prada[ i ] = A[ i ] (pentru ca jefuieste obligatoriu si casa i,deci i-1 nu este jefuita) + max(prada[i-2],prada[i-3]) - adica prada[i-2] ar insemna ca este jefuita si casa i-2 deci i-3 nu este jefuita,iar prada[i-3] inseamna ca i-3 este jefuita,i-2 nefiind in acest caz jefuita

Pai asta e o problema clasica de dinamica.
Am nota prada[ i ] = prada maxima pe care ar lua-o hotul daca jefuieste "optim" in intervalul caselor 1...i,jefuind obligatoriu casa i
Deci prada [ i ] = A[ i ] + max(prada[i-2],prada[i-3]) , cu initializarile prada[0]=0, prada[1]=A[1], prada[2]=A[2] , eventual si prada[3]=A[3]+A[1] , iar recurenta o rulezi pentru i=4,n sau i=3,n

Scuze ca postez aici la un an de la ultimul post sau daca nu e locul bun,dar as dori sa stiu daca s-ar mai organiza acest concurs(onsite si pe infoarena) si in 2011,desi deja au trecut toate concursurile internationale de informatica si nu si-ar mai avea rostul propus de antrenare pentru acestea    Caci in afara de acesta sa inteleg ca nu ar mai urma sa fie organizat vreun alt concurs pe infoarena pana la inceputul anului scolar/pana la viitoarea editie a Algoritmiadei 

N-am apucat inca sa ma uit atent pe problema si pe sursa ta,dar din ce am zarit asa "dubios" in sursa, te-as sfatui sa incerci pe moment sa refaci portiunea unde ai folosit switch,intrucat contine 4 break-uri care in general sunt mari consumatoare de timp   Incearca cu if 

Poate cineva sa imi dea un indiciu macar despre cum ar trebui abordata problema(cum trebuie folosit deque cu sumele partiale)   ?
Am incercat ceva variante de genul queue cu left si right,din care variantele mai dubioase care imi picau niste exemple au luat 50pct,iar varianta care trece exemplele mele si care imi pare mai in regula ia 10pct , dar bineinteles observ ca niciuna dintre ele nu poate gasi suma maxima in anumite cazuri 

Asta ar fi o sursa de 10pct(care bineinteles nici nu foloseste practic sumele partiale decat la o banala initializare)  

Cod:

        ifstream fin("sum2.in");
	fin>>n>>L>>U;
	for(i=1;i<=n;i++)
	{
		fin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	fin.close();
	suma=sum[L];
	size=L;
	left=1;
	right=L;
	sol=sum[L];
	while(right<n && left<=right)
	{
		if(size<U)
		{
			done=false;
			while(a[right+1]>=0 && size<U && right<n)
			{
				done=true;
				right++;
				size++;
				suma=suma+a[right];
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
			if(done==false)
			{
				right++;
				size++;
				suma=suma+a[right];
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
		}
		if(size>L)
		{
			done=false;
			while(a[left]<=0 && size>L)
			{
				done=true;
				size--;
				suma=suma-a[left];
				left++;
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
			if(done==false)
			{
				size--;
				suma=suma-a[left];
				left++;
				if(size<=U && size>=L)
					sol=max(sol,suma);
			}
		}
	}
	ofstream fout("sum2.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;

Poate cineva sa ma ajute cu vreo idee?  

Poti sa incerci ideea cu sortarea, nu cred ca sunt sanse sa iei tle, si eviti sa te complici.

Ca sa nu astepti sa ma uit pe sursa, iti dau link catre sursa mea, e destul de intuitiv scrisa, si poti sa compari cu ce ai facut tu:  http://infoarena.ro/job_detail/553869?action=view-source.

Gata,am luat 100pct facand sortarea (http://infoarena.ro/job_detail/597208). Mersi de ajutor 

Poate sa ne povesteasca un elev actual al ICHB-ului (olimpic la informatica) despre cum este viata de zi cu zi a lui in cadrul ICHB (de ce privilegii se bucura,cum se desfasoara pregatirile + diverse alte aspecte) ? 

Din ce stiu, ar trebui sa-ti mearga prima idee de afisare, insa nu am avut timp sa ma uit pe sursa ta.

Mai simplu, daca stii muchiile unei componente, poti adauga nodurile fiecarei muchii (x,y) intr-un vector, sortezi vectorul, si afisezi doar elementele distincte.

Asta se poate realiza intr-un mod destul de simplu. (if A[ i ] != A[i - 1] afiseaza A[ i ], ai grija la A[0] ! ).

Pai da,s-ar putea si asa,adica fiecare nod ar aparea de 2 ori,dar sortarea nu ar mai mari complexitatea inutil?  Cand ai sa ai timp poti sa te uiti pe sursa mea sa vezi totusi de ce nu ar fi bun? 

Am facut aceasta problema cu implementare de O(n+m) - liste de adiacenta alocate dinamic , dar ma incurca foarte tare modul in care trebuie afisate componentele biconexe (atunci cand le determin , in loc sa le afisez,trebuie sa le numar si sa le retin cumva undeva ca sa le afisez mai tarziu). Am incercat aici http://infoarena.ro/job_detail/596464 sa retin componentele in liste alocate dinamic in felul urmator : cand extrag o muchie [x,y] a componentei biconexe din stiva , retin nodul x in lista ; daca la finalul determinarii acelei componente biconexe am retinut in lista componentei doar un nod , atunci il retin si pe y. Asta deoarece muchiile sunt retinute in modul [x1,x2] [x2,x3] .... [xn,x1]  
Si totusi cum de mi se zice ca pe 8 teste am afisat gresit componentele?   Inainte mai facusem o varianta in care retineam din muchia [x,y] si pe x si pe y,iar apoi la afisare pentru fiecare componenta reinitializam un vector bool "afisat" pentru a nu afisa de 2 ori acelasi nod,dar bineinteles ca din cauza reinitializarii la fiecare componenta se facea O(n^2) sau chiar mai mult si deci lua 70pct cu TLE pe ultimele 3 teste  

Poate sa-mi explice cineva de ce gandirea mea de afisare din prima varianta ar fi gresita?  

LE : m-am mai uitat pe teste si am incercat sa mai repar la afisare cu diverse variabile prim,ultim,etc. si cu ceva verificari dar inca raman 6 teste cu afisarea incorecta   http://infoarena.ro/job_detail/596484
Deci imi poate da cineva o idee cum afisez eficient si corect nodurile componentei biconexe stiind muchiile?  

Se poate lua 100pct cu Kruskal cu sort-ul din STL ? (fara vreun min-heap pentru selectarea mai eficienta a muchiei de cost minim ?) Ca eu am incercat asa si iau doar 80pct cu 2 TLE-uri http://infoarena.ro/job_detail/595463 , am parsat apoi si citirea si tot nu intra cele 2 teste in limita de timp http://infoarena.ro/job_detail/595476  

(stiu ca nu s-a mai postat de ceva vreme,dar am nevoie de ajutor)

Poate sa-mi explice cineva sau macar sa-mi dea un indiciu despre rezolvarea corecta(cu 2 cozi din cate inteleg) ? Eu iau 60 cu memory exceeded folosind o coada alocata dinamic care bineinteles baga de prea multe ori acelasi element si depaseste memoria   Am folosit si acea codificare a coordonatelor sugerata de Adrian Airinei,dar nu rezolva asta problema cu memoria

Cod:

        inc=0;
	C=(Coada *)realloc(C,sizeof(Coada));
	C[inc].poz=(x1<<10)+y1;
	C[inc].c=a[x1][y1];
	vizitat[x1][y1]=true;
	while(sf<=inc)
	{
		aux=C[sf++];
		x=(aux.poz>>10);
		y=(aux.poz&1023);
		cost=b[x][y];
		for(k=0;k<4;k++)
		{
			if(a[x+dx[k]][y+dy[k]]!=-1)
			{
				if(a[x+dx[k]][y+dy[k]]!=aux.c)
					costnou=cost+1;
				else
					costnou=cost;
				if((b[x+dx[k]][y+dy[k]]==0 && !vizitat[x+dx[k]][y+dy[k]]) || b[x+dx[k]][y+dy[k]]>costnou)
				{
					b[x+dx[k]][y+dy[k]]=costnou;
					vizitat[x+dx[k]][y+dy[k]]=true;
					inc++;
					C=(Coada *)realloc(C,(inc+1)*sizeof(Coada));
					C[inc].poz=((x+dx[k])<<10)+y+dy[k];
					C[inc].c=a[x+dx[k]][y+dy[k]];
				}
			}
		}
	}

LE : s-a rezolvat,am luat 100pct   Mersi Magnus pentru indicatii 

Poate sa-mi explice si mie cineva care e problema cu testul 13 de iau TLE pe o implementare O(n+m) cu BFS,graf memorat prin liste de adiacenta alocate dinamic(nu cu STL),citire cu cstdio si conditie de oprire din BFS cand a gasit solutia?  

LE : Gata,am parsat citirea si am luat 100pct  Mersi eudanip