1218 Edist

[•wefgef]

Aici puteţi discuta despre problema Edist.

[•VisuianMihai]

Se poate optimiza programul cumva in functie de k? Iau tle pe ultimele 3 teste...

[•SpiderMan]

Da citeste solutiile oficiale.

[•VisuianMihai]

Cum sa fie coloane intre intervalul i-k si i+k daca i merge pana la n???
si nu trebuie |i-k| ?

[•SpiderMan]

Fii atent, al doilea for tu il ai de la 1 -> N, si cum iti spune ca rezultatul e maxim K, de aici rezulta ca pentru orice linie i, nu trebuie sa parcurgi coloanele de la 1 -> N, ci doar de la i - K pana la i + K, ceea ce este in afara acestor coloane (adica coloanele din intervalul [1, i - K) si (i + K, N] au valoarea > K). Deci trebuie doar sa modifici dinamica, si ... cam asta e.

[•noru]

iau 90 cu WA la testul 7 ce e asa special la el ?

[•horeste12]

Primesc SIGABRT daca trimit o sursa care are modificat doar un for:
In loc de

Cod:

for(int j=i-k;...)

In cea cu SIGABRT este

Cod:

for(int j=(i-k>1?i-k:1);...)

In rest este identica cu alta care ia 80 de puncte. De ce ? Acelasi lucru se intampla si daca fac o functie de maxim si scriu

Cod:

for(int j=maxim(i-k,1);...)

sau daca scriu

Cod:

int j=i-k;
if(j<1)
  j=1;
for(;...)

cod complet al for-ului:

Cod:

for(int i=1;i<=n+1;i++)
	{
		for(int j=i-k;j<=minn(i+k,m+1);j++)
		{
			if(s1[i-1]==s2[j-1])
				d[1][j]=d[0][j-1];
			else
				d[1][j]=minim(d[0][j],d[0][j-1],d[1][j-1])+1;
		}
		regulate(i);
	}