Am incercat cu hash si multimi disjuncte, insa iau 80 de puncte. Care ar fi ideea de 100 sau ce optimizari ar mai trebui sa fac?

Ai dreptate, dar in cazul acesta nu stii exact cum se comporta programul, iar incercand sa optimizezi poti gresi ceva. In fine, multumesc pentru informatii!

Si se va lua in considerare doar ultima submisie?

De ce nu mai putem trimite solutii la Pariuri ? Imi tot da submisie ignorata...

[Pentru ca sa implementezi Dijkstra pe Heap-uri ai nevoie de un Min-Heap !]

spuneti-mi va rog de ce sursa asta http://www.infoarena.ro/job_detail/985164?action=view-source are TLE pe 5 teste? folosesc o coada de prioritate in loc de heap, iar daca inlocuiesc priority_queue-ul cu un queue simplu intra in timp. Multumesc anticipat

Pentru ca sa implementezi Dijkstra pe Heap-uri ai nevoie de un Min-Heap !
priority_queue < type > e max-heap. Pentru a implementa Min-Heapul folosind STL faci asa:

Cod:

priority_queue <nod, vector<nod> , greater<nod> > MINHEAP;

Sau iti poti face propria ta clasa de comparare, ca aici: http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

Pentru mai multe informatii consulta asta : http://www.cplusplus.com/reference/queue/priority_queue/ .

Spor!

Salut, am si eu o problema si as vrea daca se poate sa mi-o explice cineva.

As vrea sa imi explice cineva cum se trece prin fiecare pas din problema.

De exemplu, pentru n=3. Ce se intampla in cod, cum functioneaza? cum circula 3-ul asta prin problema.

Cod:

#include<iostream>
using namespace std;

const MAX=20;
int n,v[MAX];

int valid(int k);
int solutie(int k);
void afisare(int k);
void BK(int k);

int valid(int k)

{
int i;
for(i=1; i<k; i++)
if(v[i]==v[k])
return 0;
return 1;
}

int solutie(int k)

{
if(k==n)
return 1;
return 0;
}

void afisare(int k)
{
int i;
for(i=1; i<=k; i++)
cout<<v[i]<<"";
cout<<endl;
}


void BK(int k)

{
int i;

for(i=1; i<=n; i++)

{
v[k]=i;
if(valid(k))

{
if(solutie(k))
afisare(k);

else

BK(k+1);
}
}
}

int main()

{
cout<<"n=";
cin>>n;

BK(1);
return 0;

}

In primul rand puteai specifica de la inceput ca este vorba despre problema generarii permutarilor de N elemente (sper ca stiai lucrul asta), astfel nu le mai dadeai dureri de cap oamenilor care nu stau sa iti citeasca postul, ci scaneaza putin sursa si se sperie ).
In al doilea rand ar trebui sa te familiarizezi cu recursivitatea ca sa intelegi ce se intampla acolo, in sursa ta. Nu cred ca daca eu sau altcineva ti-ar spune pasii algoritmului ai invata foarte mult. Fa putin debug! Afiseaza-ti cand bagi in stiva nivelul ei si elementul curent. Uite aici poti rezolva problema asta (http://www.infoarena.ro/problema/permutari) si, fiind din arhiva educationala, ai acces la sursa oficiala cat si a tuturor userilor de top, ai comentarii din care sa intelegi ce si cum face algoritmul in cauza, plus ca ai o groaza de alte site-uri de unde poti afla informatii cate vrei!
In incheiere daca vrei sa te pui la punct cu metoda backtracking iti sugerez, pentru inceput, sa faci atat problema de mai sus cat si urmatoarele :
http://www.infoarena.ro/problema/submultimi
http://www.infoarena.ro/problema/combinari
Enjoy!

Buna.
Iau 90 de puncte cu WA pe primul test. Imi puteti da un exemplu asemanator cu acesta? Am implementat ideea cu deque-uri. Multumesc anticipat.

Hmm, acum am inteles cum ai facut. Nustiu daca putem spune ca o formula e mai complicata sau mai simpla, nu depinde de lungimea formulei dar de faptul cum o deduci. In fine, imi plac problemele de dinamica unde poti aplica mai multe formule de recurenta in dependenta de cum tratezi subiectul.
Nice problema. 

Total de acord  !

Mi se pare destul de complicata formula ta.

Formula mea e aceasta si se bazeaza pe explicatia pe care am dat-o anterior. Si mi se pare mult mai simpla si intuitiva.

sum[nod] = sum[tata] + n - 2*(nodes[nod]+1);

Practic in primul dfs trebuia sa calculez doar nodes[i ] 1 <= i <= n si sum[1] ;
Iar in al doilea dfs ma foloseam de formula.

Sa zicem ca te aflii in nodul X, iar Y este un fiu al lui X.

Cand te muti din X in Y te apropii de nr[Y ] (+1 , in functie de cum iti este construit vectorul nr ) noduri (distantele pana la aceste noduri scad cu o unitate). Pe de alta parte te departezi de N- nr[Y ] ,  adica distantele pana in aceste noduri cresc cu o unitate. Stiind sum [x ] (fiindca pentru nodul 1 cunosti suma ceruta de problema ), ceea ce ramane de calculat e sum [y] pe baza a ceea ce ti-am zis mai sus.

Daca nu intelegi trimite-mi un PM si te ajut mai departe. Spor  !

ok..am citit solutia de la cezar si aia e greedy..as fi curios cum arata dinamica aici ? 

Eu nu am rezolvat inca Cezar, nu stiu cum e acolo. Am facut insa o dinamica cam asa:
Pentru inceput pornesc un dfs din nodul 1 si calculez pentru fiecare nod suma distantelor de la nodul respectiv la toate nodurile din subarborele sau (fie acesta vectorul sum ). El se afla usor folosindu-te si de un vector nrNod[i ] = numarul de noduri din subarborele lui i.

Avand calculat acest vector, pornesti o alta parcurgere df ca sa adaugi pentru fiecare nod suma distantelor "in sus" . Incearca sa te gandesti care va fi urmatoarea formula, iar daca nu iti iese trimite-mi un PM si iti explic, nu vreau sa stric farmecul acestei probleme  .

Buna.
Cred ca iarasi sunt probleme cu evaluatorul acestei probleme. Primesc urmatorul mesaj in feedback:

Cod:

Raport evaluator

Contactează autorul problemei:
Evaluatorul nu a returnat un număr la stdout pe testul 1 (se ignoră spaţii, newline, etc)

Da. Lasa plus minus si incearca algoritmul lui Tarjan pentru componentele conexe .

In legatura cu postul lui Dragos Oprica (stiu ca a trecut ceva vreme).
Pentru cei care folosesc set pentru a avea nodurile dintr-o componenta conexa in ordine crescatoare, iar mai apoi si aceste seturi ordonate tot crescator, cel mai bine este sa folositi stl pana la capat astfel :

Cod:

set < set < int > > ctc

Aceasta problema nu se poate deschide.

O fraza se poate intinde pe mai multe linii. Eu am citit caracter cu caracter si am luat 100, deci nu cred ca asta ar putea fi problema. Daca citesti linie cu linie ai grija sa incrementezi de fiecare data indexul, altfel iti poate intra in ciclu infinit.

Iei TLE pentru ca solutia ta nu e optima. Nu e nevoie sa faci un DFS din nodul i in toate nodurile. Gandeste-te cum te poate ajuta sortarea vectorului de costuri.
Bafta!

Nu inteleg de ce nu merge ca am facut 2 Lee-uri si am pus if-uri cu toate cazurile cand apara tinta si am retinut minimurile (cand este pe aceeasi linie sau coloana cu sursa,cand e pe diagonala daca e posibil si cand robotul e in acelasi loc cu sursa ) .Am pus si marimea cozii mai mare,dar inca iau killed by signal 11 la cateva teste + ca unele teste nu merg.

Cod:

#include<cstdio>
using namespace std;
#define kmax 500000
int n,T1,T2,S1,S2,S3,S4,R1,R2,R3,R4,k,min1=1001,min2=1001,min3=1001,min4=1001;
int mat[1001][1001],mat2[1001][1001];
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
int q1[kmax][3],q2[kmax][3];
int abs(int plm){
	if(plm<0)
		plm=-plm;
	return plm;
}
int max(int a,int b){
	if(a>b)
		return a;
	return b;
}
int min(int a,int b){
	if(a<b)
		return a;
	return b;
}
int zid(int i,int j){
	int j2=j,l1=1,l2=1;
	while(mat[i][j2+1]==-1){
		j2++;
		l1++;
	}
	while(mat[i+1][j]==-1){
		i++;
		l2++;
	}
	if(l1>l2)
		return l1;
	return l2;
}
int Lee (){
	int p,u,xnou,ynou,tmp,x,y,d;
	q1[1][1]=R1;q1[1][2]=R2;
	q2[1][1]=R3;q2[1][2]=R4;
	for(p=1,u=1;p<=u;p++){
		x=q1[p][1];y=q1[p][2];
		for(d=0;d<4;d++){
			xnou=x+dx[d];
			ynou=y+dy[d];
			if(xnou>=1 && xnou<=n && ynou>=1 && ynou<=n && mat[xnou][ynou]==0){
				mat[xnou][ynou]=mat[x][y]+1;
				q1[++u][1]=xnou;
				q1[u][2]=ynou;
				if((xnou==S1 && xnou==T1 && ynou>min(S2,T2) && ynou<max(S2,T2))||(ynou==S2 && ynou==T2 && xnou>min(S1,T1) && xnou<max(S1,T1))){
					if(mat[xnou][ynou]<min1)
						min1=mat[xnou][ynou];
				}
				if((xnou==S3 && xnou==T1 && ynou>min(S4,T2) && ynou<max(S4,T2)) || (ynou==S4 && ynou==T2 && xnou>min(S3,T1) && xnou<max(S3,T1))){
					if(mat[xnou][ynou]<min2)
						min2=mat[xnou][ynou];
				}
				if(abs(xnou-S1)==abs(ynou-S2) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S1,T1) && xnou<max(S1,T1) && ynou>min(S2,T2) && ynou<max(S2,T2)){
					if(mat[xnou][ynou]<min1)
						min1=mat[xnou][ynou];
				}
				if(abs(xnou-S3)==abs(ynou-S4) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S3,T1) && xnou<max(S3,T1) && ynou>min(S4,T2) && ynou<max(S4,T2)){
					if(mat[xnou][ynou]<min2)
						min2=mat[xnou][ynou];
				}
				if(xnou==S1 && ynou==S2){
					if(mat[xnou][ynou]<min1)
						min1=mat[xnou][ynou];
				}
				if(xnou==S3 && ynou==S4){
					if(mat[xnou][ynou]<min2)
						min2=mat[xnou][ynou];
				}
			}
		}
	}
	for(p=1,u=1;p<=u;p++){
		x=q2[p][1];y=q2[p][2];
		for(d=0;d<4;d++){
			xnou=x+dx[d];
			ynou=y+dy[d];
			if(xnou>=1 && xnou<=n && ynou>=1 && ynou<=n && mat2[xnou][ynou]==0){
				mat2[xnou][ynou]=mat2[x][y]+1;
				q2[++u][1]=xnou;
				q2[u][2]=ynou;
				if((xnou==S1 && xnou==T1 && ynou>min(S2,T2) && ynou<max(S2,T2))||(ynou==S2 && ynou==T2 && xnou>min(S1,T1) && xnou<max(S1,T1))){
					if(mat2[xnou][ynou]<min3)
						min3=mat2[xnou][ynou];
				}
				if((xnou==S3 && xnou==T1 && ynou>min(S4,T2) && ynou<max(S4,T2)) || (ynou==S4 && ynou==T2 && xnou>min(S3,T1) && xnou<max(S3,T1))){
					if(mat2[xnou][ynou]<min4)
						min4=mat2[xnou][ynou];
				}
				if(abs(xnou-S1)==abs(ynou-S2) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S1,T1) && xnou<max(S1,T1) && ynou>min(S2,T2) && ynou<max(S2,T2)){
					if(mat2[xnou][ynou]<min3)
						min3=mat2[xnou][ynou];
				}
				if(abs(xnou-S3)==abs(ynou-S4) && abs(xnou-T1)==abs(ynou-T2) && xnou>min(S3,T1) && xnou<max(S3,T1) && ynou>min(S4,T2) && ynou<max(S4,T2)){
					if(mat2[xnou][ynou]<min4)
						min4=mat2[xnou][ynou];
				}
				if(xnou==S1 && ynou==S2){
					if(mat2[xnou][ynou]<min3)
						min3=mat2[xnou][ynou];
				}
				if(xnou==S3 && ynou==S4){
					if(mat2[xnou][ynou]<min4)
						min4=mat2[xnou][ynou];
				}
			}
		}
	}
	tmp=min(max(min1,min4),max(min2,min3));
	return tmp;
}
	
int main(){
	int i,j,maxz=0,xx,yy,timp;
	freopen("ai.in","r",stdin);
	freopen("ai.out","w",stdout);
	scanf("%d",&n);
	scanf("%d%d%d%d%d%d%d%d%d%d",&T1,&T2,&S1,&S2,&S3,&S4,&R1,&R2,&R3,&R4);
	scanf("%d",&k);
	for(i=1;i<=k;i++){
		scanf("%d%d",&xx,&yy);
		mat[xx][yy]=-1;
	}
	mat[T1][T2]=-2;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			mat2[i][j]=mat[i][j];
			if(mat[i][j]==-1)
				if(zid(i,j)>maxz)
					maxz=zid(i,j);
		}
	}
	timp=Lee();
	printf("%d\n",maxz);
	printf("%d\n",timp);
	return 0;
}

Cred ca si tie ti-e greu sa intelegi ce si cum ai facut, asa ca nu te astepta la vreun raspuns la intrebarea ta, "De ce nu merge?". Cred ca cel mai bine ar fi sa faci LEE folosind coada ( queue ) din STL. Ca sa intelegi  mai bine cum functioneaza recomand problema Pietre2 de pe infoarena. Eu acolo am invatat cum si ce face queue-ul...
Sau daca nici asta nu te convinge sa inveti STL, atunci gandeste-te sa folosesti coada aceea circular.
Adica functiile, sau oriunde faci introducerea si extragerea unui elemnt din coada sa fie cam asa :

Cod:

void intr ( int c, int d )
{
       u=u+1;
       //Aici e smecheria, daca dai de limita cozii, incepi de la inceput
       if(u>20000)
            u=1;
       q[1][u]=c;
       q[2][u]=d;
} 
//extrag un element din coada
void extr(int &c,int &d)
{
     p=p+1;
     //La fel procedezi si in cazul extragerii
     if(p>20000)
           p=1;
     c=q[1][p];
     d=q[2][p];
}

Cam astea ar fi modalitatile pe care eu le stiu pentru ca sa scapi de KBS si incorect.

Dupa un cuvant poate fi pus un singur spatiu?

Nu trebuia "Vom numerota aceste seri incepand cu 0." ?

Eu credeam ca e chiar invers   .
Merci

Eu la problema asta luam 80 de puncte cu i si j declarate global...
Dupa ce am facut asa

Cod:

for(int i=1; i<=...)

am luat 100 .
Destul de ciudat  . Cam care ar fi explicatia ?

Ce insemna "Killed by signal 8(SIGFPE)" ?
L.E. Las-o balta, am reusit  .

Distantele sunt sortate in fisierul de intrare?

Nu intra in timp solutia pentru determinarea secventei folosind dooi vectori, respectiv l[ i ] si urm[ i ]??
Eu asa fac subsirul de lungime maxima si iau 70 de puncte cu TLE pe restul testelor.