Salutare!

In 2 luni o sa ma mut in San Francisco sa lucrez pentru un start-up, si sunt curios daca mai exista romani tineri prin zona aia
Sper ca am postat unde trebuie...

- Radu

Am avut noroc cu corectorii ( de la Colegiul National "Mircea cel Batran" Constanta) ... am luat 9,80.

Salutare !
Stiti cumva cand au loc inscrierile pentru FMI ? Site-ul de 10 zile nu le mai merge, deci sunt total pe dinafara.

Aveti cumva idee cine se ocupa de contestatii ? E vreo comisie speciala la Bucuresti ? Sau iar o sa dau peste niste profesori incapabili   A ajuns sa-mi traga informatica ( 8.70 ) media in jos...

Si am avut o singura greseala minuscula... am pus for(i=1;i<=s1;i++) in loc de for(i=1;i<=s1 && i<=9;i++) la ultima problema. Dar de aici pana la 8.70.... of....

Nu ar merge asa... profesorii trebuie sa-si dea seama ce a vrut sa faca elevul. Daca spre exemplu un elev baga un quicksort la ultima problema si scrie un algoritm de o pagina , dar greseste o variabila ? Then what ?

E clar... daca folosesti mai mult de 2 variabile si un for in program, bagi corectorii in ceata.

Nu pot sa cred asa ceva... Corectorii de la proba de informatica sunt incompetenti din toate punctele de vedere. Un tip rezolva ultima problema cu un for , de la 10000 la 99999, iar la explicatie spune ("Programul este eficient pentru ca ia doar numerele de 5 cifre") . A luat 10 curat. Asta e bataie de joc da-o incolo. Si asa au facut la toti !!!! Cei ce au rezolvat problema INEFICIENT au luat 10 puncte. RESTUL SUB 5. Rusine sa le fie profesorilor corectori !!!!!!!!!!!!!!!!!!!!!!

Puteti va rog sa-mi descrieti solutia de complexitate O(n*Logn) la aceasta problema ? Multumesc !

Un cuvânt este anagramã a altui cuvânt dacã este format din exact aceleaºi litere, aranjate într-o
altã ordine. Exemplu: caras si scara.
b) Dându-se o mulþime de n cuvinte peste alfabetul {a ,........, z}
sã se verifice dacã printre elementele mulþimii date existã anagrame.

Trebuia sa afli lungimea drumului de cost minim ce trece prin toate cele K puncte. Deci nu trebuia sa treci de mai multe ori prin acelasi oras.

Problema ubuntzei am facut-o printr-o simpla parcurgere in adancime. Oare ce punctaj scoate ? Peste 30 ?

Deci... cum a fost ?
E frustrant faptul ca ambele probleme au fost din aceeasi categorie.

In problema de mai sus spre exemplu, aveam de transpus un vector de tip char, intr-o matrice de tip char + un vector de tip int. (Alta idee pe langa folosirea unui fisier auxiliar nu mi-a venit. )

Citirea am facut-o cu ajutorul unui vector de tip char:
Fisier.in:

Cod:

(((((((unt 20 ou 4 apa 500)10 rom 100 apa 20 zahar 2 abracadabraabracadab 5)30 zaha 10 abracadabraabracadab 50)99(apa 10 zahar 20 unt 100 apa 999)5)30(a 1 b 1 c 1 apa 25 abracadabraabracadab 5)20)10 abracadabraabracadab 150)4 abracadabraabracadab 52)98

Dupa preprocesare, am facut afisarea (de caractere) in fisierul auxiliar:
fisier.aux

Cod:

unt 20
ou 4
apa 500
rom 100
apa 20
zahar 2
abracadabraabracadab 5
zaha 10
abracadabraabracadab 50
apa 10
zahar 20
unt 100
apa 999
a 1
b 1
c 1
apa 25
abracadabraabracadab 5
abracadabraabracadab 150
abracadabraabracadab 52

Pentru recitire, am folosit o matrice de cuvinte, si un vector de tip int, pentru a retine valorile corespunzatoare fiecarui ingredient (afisate initial sub forma de caractere).
Restul e can-can.
 

si nu ar trebui sa fie permis nici pe infoarena.

De ce nu ?

Esti sigur ? Eu m-am uitat peste regulament si nu am sesizat nicio astfel de precizare.
Am trimis niste solutii bazate pe folosirea de fisiere auxiliare atat pe infoarena cat si pe campion, si nu am avut probleme la evaluare.
Exemplu: (Problema Reteta2)

Cod:

#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
int i=1,j,n,s=0,nr,inc,ii,sum,tot=0,u2,u,vc[1000];
char v[1020],v2[1000],v3[1000][1000];
int trans(char x)
{
	if(x=='9') return 9;
	else if(x=='8') return 8;
	else if(x=='7') return 7;
	else if(x=='6') return 6;
	else if(x=='5') return 5;
	else if(x=='4') return 4;
	else if(x=='3') return 3;
	else if(x=='2') return 2;
	else if(x=='1') return 1;
	else if(x=='0') return 0;
	return 10;
}
int check(int x,int y)
{
	int z;
	z=strlen(v3[x]);
	for(i=0;i<=z;i++)
		if(v3[x][i]>v3[y][i])
			return 2;
		else if(v3[x][i]<v3[y][i])
			return 3;
		return 0;
}
int main()
{

	ifstream f("reteta2.in");
	while(f>>v[i])
	{
		i++;
	}
	//cout<<v[30]<<" ";
	for(j=0;j<=i;j++)
		if(v[j]==')' && trans(v[j+1])<10)
		{
			nr=0;
			inc=j+1;
			while(trans(v[j+1])<10)
			{
				nr++;
				j++;
			}
			sum=0;
			for(ii=inc;ii<=j;ii++)
			{
				sum=sum*10+trans(v[ii]);
				v[ii]=' ';
			}
			v[inc-1]=' ';
			tot+=sum;
		}
		else if(v[j]=='(' || v[j]==')')
			v[j]=' ';

	ofstream g("reteta2.out");
	g<<tot<<'\n';
	//u2=2;
	int n=0;
	for(j=1;j<=i;j++)
		if(v[j]!=' ')
		{
			n++;
			v2[n]=v[j];
		}
	int tot2=0;
	ofstream g2("reteta2.aux");
	for(j=1;j<=n;j++)
		{ 
			if(trans(v2[j])<10 && trans(v2[j])>=0) u=2;
			else u=1;
			if(trans(v2[j+1])<10 && trans(v2[j+1])>=0) u2=1;
			else u2=2;
			if(u==2 && u2==2)
			{
				g2<<v2[j]<<'\n';
				tot2++;
			}
			else if(u==1 && u2==1)
			{
				g2<<v2[j]<<" ";
			}
			else g2<<v2[j];
			//else if(u==
		}
	g2.close();
	ifstream f2("reteta2.aux");
	for(j=1;j<=tot2;j++)
	{
		f2>>v3[j]>>vc[j];
	//	cout<<v3[j]<<" "<<vc[j]<<'\n';
	}
	int ccc=0,viz[1001],jj,sol[1000],nrrr=0;
	for(j=1;j<=tot2;j++)
	{
		if(!viz[j])
		{
			nrrr++;
			sol[nrrr]=j;
			for(jj=j+1;jj<=tot2;jj++)
				if(!check(j,jj) && !viz[jj])
				{
					vc[j]+=vc[jj];
					viz[jj]=1;
				}
			viz[j]=1;
		}
	}
	//for(j=1;j<=nrrr;j++)
	//cout<<v3[sol[j]]<<" "<<vc[sol[j]]<<'\n';
	int aux;
	
	for(j=1;j<=nrrr;j++)
		for(jj=j+1;jj<=nrrr;jj++)
			if(check(sol[j],sol[jj])==2)
			{
				aux=sol[j];
				sol[j]=sol[jj];
				sol[jj]=aux;
			}
	
	for(j=1;j<=nrrr;j++)
		g<<v3[sol[j]]<<" "<<vc[sol[j]]<<'\n';
	
}

Este permisa folosirea de fisiere auxiliare la OJI/ONI ?
Spre exemplu, daca doresc sa schimb structurile folosite de program, imi vine mai usor sa fac o afisare intr-un fisier auxiliar , urmand apoi sa le recitesc sub alt format, decat sa fac atribuirile manual. Nu e cea mai eficienta metoda, dar te salveaza de o gramada de eforturi.

Tocmai asta e...elementele trebuie sa fie asezate in ordine.
Mie mi se da un vector, iar eu trebuie sa sterg si sa mut anumite elemente din vector in capat, pe baza unor anumite conditii.
Singura solutie relativ eficienta la care m-am gandit ar fi sa maresc permanent numarul de elemente din cadrul vectorului, sa copiez elementele , dupa caz, in pozitiile superioare nou create, iar cele initiale sa primeasca valoare 0 sau NULL, ajungand apoi sa fie ignorate total de catre program.
Daca lucrez insa asa, voi ajuge sa am extrem de multa memorie risipita...

Care este cea mai eficienta metoda de stergere a unei valori dintr-un vector ?
Exemplu: Pentru vectorul cu valori v[5] = {1,2,3,4,5}, sa se stearga valoarea lui v[3], aceasta fiind in schimb inlocuita de cea a lui v[4] (analog pentru v[4] si v[5] daca vectorul ar fi fost mai mare)

Pot aloca memorie (in mod static) unui tablou bidimensional, fara a-l face patratic ? Simplu spus, spatiul de memorie alocat dimensiunii 2 sa depinda de dimensiunea 1 :
Ex:
a[1][1]
a[2][1],a[2][2]
a[3][1],a[3][2],a[3][3]

Metoda greedy obtine 10 puncte si nu tine cont de k....

Ca sa verific k-ul as fi putut sa implementez de mai multe ori dijkstra (de 9 ori maxim, din moment ce k era intre 2<10) ... sau as fi putut sa construiesc muchiile treptat, pe baza celor vizitate anterior  .

Oricum, chiar si daca nu as fi verificat k-ul, sunt sigur ca ar fi obtinut >= 30 puncte.

Nu am luat nimic pentru ca nu am avut timp sa il termin
Ideea era sa initializez o variabila cu valoarea lui a[1][1], dupa care sa aflu distanta maxima (cu inversare de semn) intre a[1][1] si a[2][n] (pe baza grafului), si odata aflata acea distanta sa afisez d[n]+x. (costul de la a[j] - a[j+1] = valoarea ce se gasea la coordonatele i,j+1. , asa ca la final ramanea valoarea lui a[1][1] neadaugata).

Se putea construi lista muchiilor impreuna cu costul astfel : a[j] - a[i+/-1][j] ,  a[j] - a[j+1] .

Teoretic ar trebui sa mearga. Insa nu am vazut Dijkstra declarat drept solutie oficiala ...

Incredibil.... eu am pierdut 50 de puncte din cauza unui while caruia nu i-am pus bine conditia de "finish" (pe exemplu a mers).

Iar la a 2-a problema nu m-am incadrat in timp. Am incercat sa implementez Dijkstra (fiecare nod sa aibe legatura cu nodurile adiacente pe verticala,respectiv orizontala) .
Stie cineva daca Dijkstra ar fi fost o solutie viabila ?

Mult succes tuturor participantilor ! Sper sa ne vedem la ONI.

Am incercat sa construiesc un algoritm de cost minim pe baza BFS si a inegalitatii triunghiului. 90% din valori sunt corecte, indiferent de input, insa uneori nu gaseste drumuri spre anumite puncte si afiseaza valoarea 0 . Spuneti-mi ce am omis va rog !!

Cod:

	for(i=1;i<=n;i++) 
		{
			if(i!=1) d[i]=INF;
			else d[i]=0;
	}
	sol[1]=1;
	u=1;
	
for(j=1;j<=n;j++)
	for(i=1;i<=n;i++)
		if(a[sol[j]][i]) 
		{
			if(j!=1) if(a[sol[j]][i]+d[sol[j]]<d[i]) d[i]=a[sol[j]][i]+d[sol[j]];
			if(j==1)if(a[sol[j]][i]<d[i]) d[i]=a[sol[j]][i];
			u++;
			sol[u]=i;
		}

Nu vreau alta sursa ! Vreau doar "corectura" !
Multumesc !

Barack Obama - Computer Science Question


that just made my day...

Nu ma astept la rezolvare ! Dar nici macar un hint ?
Iar daca as fi stiut ca asta este 'lair-ul' autorilor, crezi ca as mai fi venit aici dupa ajutor ?

Daca nu imi poti lasa un hint... nici o problema (oricum nu particip la campion,dar s-a gasit cineva sa-mi propuna aceasta problema)... insa o sa te rog sa-mi spui/dai algoritmul la incheierea rundei.Sau mai degraba un fir logic...