346 Padure

[•razyelx]

Interesanta ideea, dar poti sa imi dai un exemplu pentru care algoritmul meu cade?

[•Mishu91]

Ai grija la coada circulara... oricum interesant ca iei WA, pt ca ar trebui sa iei TLE (tu adaugi un element in coada de mai multe ori)

[•razyelx]

Pai adaug un element dupa conditiile care le-am pus mai sus. Eu zic ca e ok. Cum altfel as putea restrictiona adaugarea?Nu prea ar trebui sa iau TLE. Dar ar fi mai bine decat WA pe 4 teste. Am incercat cum ai zis si tu: cu doua cozi. Algoritmul e ceva de genu:

cat timp coada 1 nu este vida{
     verifica vecinii lui a[x1][y1]{
        daca a[x2][y2] == a[x1][y1]

               daca b[x2][y2] > b[x1][y1] || b[x2][y2]  , b[x2][y2] = b[x1][y1] si adaug elementul in coada 1
   
        daca a[x2][y2] != a[x1][y1]
               
               daca b[x2][y2] > b[x1][y1]+1 || b[x2][y2]==-1  , b[x2][y2] = b[x1][y1]+1 si adaug elementul in coada 2
     }
     daca coada 1 este vida
            daca coada 2 nu este vida
                   preia in coada 1 primul element din coada 2
}
Dar iau doar 40 de puncte pe el. Deci era mai bun celalalt.

[•Mishu91]

Ceva de genu am facut si eu Ai grija sa nu-ti crape cand faci coada circulara.
Daca vrei iti trimit sursa, poate te lamuresti mai bine

[•stocarul]

Ma cam supara problema asta
Am facut prima data o rezolvare cu Bellman Ford, si obtin 60 pct (restul TLE)
Acum...m-am gandit sa fac cu Dirjkstra....si obtine 90 pct (TLE pe testul 9)
Ce rezolvare ar trebui sa aplic?

p.s. rezolvare pt 100 pct 

[•Mishu91]

Cred ca te-ai complicat putin cu Dijkstra... merge un bf putin mai smecher (vezi ideea cu 2 cozi)

[•stocarul]

Cred ca te-ai complicat putin cu Dijkstra... merge un bf putin mai smecher (vezi ideea cu 2 cozi)

De ce sa am doua cozi?
Nu e mai bine daca am o singura coada circulara?

LE: Am luat 100 pct cu Dijkstra cu citirea parsata

[•wefgef]

Daca citesti posturile anterioare cu multa atentie, vei vedea ca problema nu este un BF simplu, e putin mai complicat - de aceea ai nevoie de 2 cozi.

[•dornescuvlad]

Eu iau 5 WA pe ultimele 5 teste cu 2 cozi de 520000 elemente. Un hint ? Se poate sa gresesc ceva ?
Eu fac un lee asa:

Cod:

 while(first<last)//cat timp mai am elemente in coada
{
		i=qi[first];
		j=qj[first];
		first++;
		
		for(int k=0;k<4;k++)
		{
			inou=i+dx[k];
			jnou=j+dy[k];
			if(A[inou][jnou]!=-1)
			{
				if(A[inou][jnou]!=A[i][j]) //cazul 1
					if(O[inou][jnou]>O[i][j]+1)
					{
						O[inou][jnou]=O[i][j]+1;
						qi[last]=inou;
						qj[last]=jnou;
						last++;
					}
					
				if(A[inou][jnou] == A[i][j]) // cazul 2 
					if(O[inou][jnou] > O[i][j])
						{
							O[inou][jnou]=O[i][j];
							qi[last]=inou;
							qj[last]=jnou;
							last++;
						}
				
			 }
}

[•vladtarniceru]

am nevoie de putin ajutor, eu iau 70 de puncte cu TLE si nu stiu ce as mai putea optimiza

eu fac asa lee-ul

Cod:

for (; !Q.empty (); ){
			stu rec = Q.front ();
			Q.pop_front ();
			for (int k = 0; k < 4; ++k){
				stu acm = rec;
				acm.i += dx[k];
				acm.j += dy[k];
				if (acm.i > 0 && acm.j > 0 && acm.i <= n && acm.j <= m){
					int val = b[rec.i][rec.j] + (a[acm.i][acm.j] != a[rec.i][rec.j]);
					if ( !b[acm.i][acm.j] || b[acm.i][acm.j] > val ){
						Q.push_back (acm);//Q[dr++] = acm;
						b[acm.i][acm.j] = val;
					}
				}
			}
		}

[•toni2007]

Verifica daca e in coada atunci cand updatezi, daca e, nu il mai baga inca o data.

[•vladtarniceru]

mersi de hint, dar e mai incet ca inainte (60 pct de data asta)... ca sa fac asta am luat o matrice c[ i ][ j ] in care verific daca apare sau nu

[•scipianus]

(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 

[•Magnus]

faci un bfs din start, apoi sa zicem ca tu ai ajuns la un nod
pt vecinii lui faci un bfs/dfs pentru copacii de aceeasi specie

sper ca am dat doar un hint  
l.e.: si bineinteles tii o matrice care sa tina minte daca elementul este sau nu in coada deja

[•VisuianMihai]

0 inseamna copac sau spatiu liber?

[•pauldb]

0 simbolizeaza un tip de copac, la fel ca celalalte numere naturale.

[•VisuianMihai]

Nu stiu de ce iau KBS pe ultimele teste... Am declarat 2 matrici de 1001*1001 si o coada de 1002001;
Nu am nicio idee pe unde iese programul din limite.
P.S: Am facut un BFS Modificat.

[•vendetta]

Am nevoie de niste sfaturi de la cei care au luat 100.
Am trimis mai multe surse printre care : bellman ford(70),  dijkstra(70);
Ultima sursa trimisa de la care ma asteptam sa i`au 100 m`a dezamagit(doar 80 cu tle pe ultime 2 teste).Am o parcurgere in latime si una in adancime. Pentru fiecare nod nou adaugat in coada fac un fill si bag in coada toti vecinii care sunt la fel. Complexitatea ar fi O (n + m) pentru ca un nod e introdus in coada doar o singura data.

[•an_drey_curent]

Si eu am problema asta de multa vreme la incercate... Cred ca solutia e :

,,Poti rezolva problema printr-o parcurgere bf (eu am facut ceva cu 2 cozi). Adica calculezi intai toate nodurile pentru care distanta este 0, apoi 1 si tot asa pana cand ai vizitat pozitia finala." . E comentariu pe prima pagina. Pare interesanta solutia asta, dar mereu mi-a fost lene sa o implementez.

Mi-am zis si eu of-ul..

[•SpiderMan]

Cam trebuie marita limita, eu cu sursa veche iau 70 pct ....

[•ctlin04]

Mda limita chiar este destul de strinsa si la memorie si la timp, daca rezolv problema cu memoria am TLE pe un test, iar daca rezolv problema cu timpul am MLE pe acelasi test, cred ca ar trebui marit timpul la 0,2 ms 

[•tzipleatud]

@Catalin: Se poate lua inca 100, daca parsezi citirea si folosesti 2 cozi, una in care pui elemente daca e egal cu elementul curent, si una normala (la limita, da, dar intra). Bafta!

[•ctlin04]

Nu prea inteleg cum sa fac cu doua cozi insa am luat 100 pina la urma cu timpul maxim ~100 ms, si memorie ~4,5 MB, adica destul de departe de limite, la fel am facut parsare apoi mi-am creat o lista circulara de 20 000 de elemente pe care am folosit-o ca coada 

[•klamathix]

Incearca sa intelegi cum se face cu 2 cozi. Sfatul meu e sa incercati sa invatati lucruri din probleme, nu sa le invingeti, i.e sa luati 100   Nu parsati si faceti incantatii ca sa mearga codul mai repede, noi vom mari limitele suficient incat sa nu fie niciodata nevoie sa faceti asta daca algoritmul e corect (cu mici exceptii gen cele ale lui Ciucu, ca acolo ala-i farmecul)

Ideea principala la solutia cu 2 cozi e ca in momentul in care expandezi un nod sa oferi prioritate vecinilor de aceeasi culoare cu el. Ceea ce inseamna ca mai tii o coada cu toti vecinii de expandat de culoarea curenta si de fiecare data cand alegi un nod pentru expandat verifici intai prima coada si treci la a doua doar daca nu mai ai nimic de aceeasi culoare. Ca sa intelegi de ce merge asta mult mai repede, gandeste-te cand merge incet Bellman-Fordul: cand are de reactualizat costul pentru acelasi nod de multe ori.

Cod:

111
122
133
144
155
111

Uita-te putin pe exemplul asta. Daca vrei sa ajungi din dreapta sus in dreapta jos si pornesti un BF, exista sansa ca el sa sa gaseasca prima oara costul 5. Apoi sa gaseasca unul de 4, etc. Daca dai prioritate 1-urilor in expandare mergi la fix din prima si nu mai reiterezi nimic.

For further reference, problema asta este un caz particular de Dijkstra cu costuri mici (aici costurile sunt doar 0 si 1). Ideea se poate adapta, e explicat destul de bine in topicul din arhiva educationala: http://infoarena.ro/forum/index.php?topic=2778.0

[•repp4radu]

Eu am incercat sa implementez varianta cu 2 cozi(prima pentru elementele pentru care nu se plateste in plus, a doua pentru cele pentru care e necesara plata unui cristal) si am luat 50p, cu 2 WA si 3 TLE. WA il iau din cauza ca daca am in prima coada sa zicem o pozitie pe care se afla un copac de tip 7 si acesta e vecin cu un copac de tip 1, pe cel de tip 1 il bag in a doua coada. Daca copacul de tip 1 are si un alt copac de tip 1 ca vecin, care se afla deja in prima coada, eu actualizam valoarea, dar nu il bagam pe 1 si in prima coada. Astfel incat nu mai era corect sa opresc algoritmul imediat dupa ce ajungeam in nodul de final(puteam avea costuri mai mici in aceeasi coada). Dar asta m-ar scapa de WA. Eu nu stiu cum pot scapa de TLE.

PS nu bag un nod in coada decat daca i se imbunatateste costul(ceea ce se intampla maxim de doua ori <initial el fiind infinit, iar mai apoi poate avea loc cazul de mai sus in care il bag in ambele cozi>)