981 Immortal

[•stef2n]

Aici puteti discuta despre problema Immortal.

[•Robytzza]

Un pik ciudat sa se dea back la 11-12 

[•dornescuvlad]

Un pik ciudat sa se dea back la 11-12  

Cand se pun cele de la a 10-a ?

[•wefgef]

Astazi vor fi adaugate problemele de la clasele a IX-a si a X-a.

[•alexandru92]

Ce optimizari pot sa fac la back ? pentru fiecare nemuritor, care nu este mort,  vad daca are vecini si daca poate sari peste ei, daca  apelez recursiv back. Cand a gasit o solutie folosesc exit ca ies de tot din program...
Obtin 90pct , TLE pe al 2 test

[•pandaemon]

Ce optimizari pot sa fac la back ? pentru fiecare nemuritor, care nu este mort,  vad daca are vecini si daca poate sari peste ei, daca  apelez recursiv back. Cand a gasit o solutie folosesc exit ca ies de tot din program...
Obtin 90pct , TLE pe al 2 test

Banuiesc ca la fiecare pas din backtracking tu ai 2 for-uri cu care se parcurge o matrice care indica daca in pozitia respectiva se afla un nemuritor sau nu. Incearca sa ajungi la O(numar_nemuritori) in loc de O(n*m) si o sa iei 100 de puncte.

[•alexandru92]

Nu parcurg nici o matrice, am un vector v in care retin toti nemuritorii si o matrice G in care retin 1 daca nemuritorul este in casuta respectiva sau 0 altfel. Si acum in back, fac un for de la 1->numarul de numritori, iar pentru fiecare nemuritor vad cei 4 vecini ai sai, vad daca poate sari peste unul si daca are peste cine sa sara, daca sunt indeplinite ambele atunci apelez back...
ps: M-am uitat peste solutia oficiala... ideea e la fel ca cea de 100pct
LE: am trimiso si pe .campion si pe testul pe care depasesc il trec cu 0.17 

[•pandaemon]

Nu parcurg nici o matrice, am un vector v in care retin toti nemuritorii si o matrice G in care retin 1 daca nemuritorul este in casuta respectiva sau 0 altfel. Si acum in back, fac un for de la 1->numarul de numritori, iar pentru fiecare nemuritor vad cei 4 vecini ai sai, vad daca poate sari peste unul si daca are peste cine sa sara, daca sunt indeplinite ambele atunci apelez back...
ps: M-am uitat peste solutia oficiala... ideea e la fel ca cea de 100pct
LE: am trimiso si pe .campion si pe testul pe care depasesc il trec cu 0.17 

Pe aceeasi idee am luat si eu 100 de puncte chiar pe infoarena. Dupa ce vezi ca un nemuritor are vecin peste care poate sari si initiezi avansarea in backtracking, cum updatezi in vectorul cu nemuritori ca cel peste care s-a sarit e mort? Daca o sa zici ca nu e aici problema, nu prea am cum sa te ajut fara sa vad sursa, deci va trebui sa te mai zbati.

[•alexandru92]

In timp constant, sa zic ca v[ i ] este nemuritorul care sare. Daca se poate sari v[ i ] va  contine noua pozitie, desigur cu update-urile necesare si in matrice...
LE: parserz si citirea, si afisarea. Oricum eu mai am o intrebare, de ce pe .campion merge sub 0.2 si pe infoarena merge peste  

[•pandaemon]

In timp constant, sa zic ca v[ i ] este nemuritorul care sare. Daca se poate sari v[ i ] va  contine noua pozitie, desigur cu update-urile necesare si in matrice...
LE: parserz si citirea, si afisarea. Oricum eu mai am o intrebare, de ce pe .campion merge sub 0.2 si pe infoarena merge peste  

Sa zicem ca nemuritorul i este pe lina x si coloana y si gaseste un nemuritor peste care vrea sa sara cu indicele i+5 care se afla pe linia x+1 si coloana y. Pe i+5 il updatezi tot in timp constant in vector ca dispare?

Practic eu am facut la fel ca tine doar ca in matrice in loc de:
"daca mat(i)(j)=1 exista nemuritor pe pozitia respectiva",
folosesc:
"daca mat(i)(j)!=0 rezulta ca pe pozitia i si j se afla nemuritorul cu indicele mat(i)(j)"

Si treaba asta ma ajuta sa fac toate update-urile in timp constant.

[•alexandru92]

Aceeasi chestie fac si eu....
LE: Asta e bucata de cod

Cod:

//pr este o structura cu doua campuri x si y 
 inline void back( int nr )
{
	
	if( nr == I-1 )
	{
		ofstream out( "immortal.out" );
		copy( from.begin(), from.end(), ostream_iterator<pr>( out ) );
		out.close();
		exit( 0 );
	}
	int i, j;
	for( i=0; i < I; ++i )
		if( 1 == G[ v[i].x ][ v[i].y ] )
		{
			for( j=0; j < 4; ++j )
			{
				pr z( v[i].x+dx[j], v[i].y+dy[j] );
				if( z.x > N || z.y > M || z.x <= 0 || z.y <= 0 || 1 == G[ z.x ][ z.y ] )
					continue;
				pr z2( v[i].x+dx2[j], v[i].y+dy2[j] );
				if( z2.x > N || z2.y > M || z2.x <= 0 || z2.y <= 0 || 0 == G[ z2.x ][ z2.y ] )
					continue;
				from.push_back( v[i] ); from.push_back( z );
				pr aux=v[i];
				v[i]=z;
				G[ z.x ][ z.y ]=1;
				G[ aux.x ][ aux.y ]=G[ z2.x ][ z2.y ]=0;
				back( nr+1 );
				v[i]=aux;
				G[ z.x ][ z.y ]=0;
				G[ v[i].x ][ v[i].y ]=G[ z2.x ][ z2.y ]=1;
				from.pop_back(); from.pop_back();
			}
		}
}

[•APOCALYPTO]

Am o intrebare!
Pot lua 100 daca folosesc un singur "nemuritor killer" care sa-i ucida pe toti ceilalati nemuritori?
In text nu se specifica dar din comentarii de mai sus eu asa inteleg.
Multumesc anticipat pentru raspuns!

[•znakeu]

Nu cred ca textul se refera la "The Immortal" Din cate imi dau seama "The Immortal" nu e despre nemuritori care se omoara intre ei...

Textul se refera la faimoasa serie "Highlander":
http://www.imdb.com/title/tt0091203/
http://www.cinemagia.ro/filme/highlander-nemuritorul-2111/#

There can be only one!

[•alexandru92]

Am o intrebare!
Pot lua 100 daca folosesc un singur "nemuritor killer" care sa-i ucida pe toti ceilalati nemuritori?
In text nu se specifica dar din comentarii de mai sus eu asa inteleg.
Multumesc anticipat pentru raspuns!

Nu, eu asta am folosit la oji si am  luat 10pct...
Nu se poate deoarece tu poti incepe cu un nemuritor, asta sa fie omorat de altul care la randul lui sa fie omorat si cel care castiga sa fie cel care n-ai fi crezut

[•APOCALYPTO]

Care aveti idee de ce una din sursele oficiale(cea cu .cpp) ia 90 de pu8ncte pe infoarena iar cea cu .c ia 100 si daca ii schimb extensia in .cpp ia tot 100?

PS:
M-am uitat peste amandoua si par sa faca acelasi lucru si sa aiba aceiasi complexitate singurele diferente fiind:
- folosirea switch-ului pentru afisare in cea de 90;
- folosirea nemuritorului ce urmeaza sa fie omorat in cea de de 90 si a celui ce urmeaza sa omoare in cea de 100.
Sa fie astea motivele?

[•freak93]

Din cate imi amintesc sursa cpp era cea scrisa de Marinel Serban si in loc sa treaca prin lista nemuritorilor(care e destul de mica) trecea prin matrice(care e de vreo 30 de ori mai mare pe cel mai mare test).
A doua sursa era scrisa de Emanuela Cerchez in C si trecea prin lista nemuritorilor.
Nu sunt sigur dar cred ca acesta ar cam fi motivul.

[•APOCALYPTO]

Din cate imi amintesc sursa cpp era cea scrisa de Marinel Serban si in loc sa treaca prin lista nemuritorilor(care e destul de mica) trecea prin matrice(care e de vreo 30 de ori mai mare pe cel mai mare test).
A doua sursa era scrisa de Emanuela Cerchez in C si trecea prin lista nemuritorilor.
Nu sunt sigur dar cred ca acesta ar cam fi motivul.

In ambele trece prin lista nemuritorilor.

[•freak93]

M-am uitat mai atent peste ele si singura diferenta majora e faptul ca in cea .cpp pentru fiecare nemuritor verifica daca are un vecin sa sara peste el, iar in cea .c pentru fiecare nemuritor se cauta un vecin peste care sa sara.
 Nici eu nu inteleg care ar fi diferenta dintre cele doua, mai ales ca in antetul primeia scrie "Backtracking neoptimizat:17s" iar in antetul celeilalte scrie "Bactraking optimizat:0.17s".

[•stocarul]

Păi există diferență prin faptul că se aleg mutările în altă ordine, și deci se ajunge mai repede la o soluție "câștigătoare".

[•APOCALYPTO]

Păi există diferență prin faptul că se aleg mutările în altă ordine, și deci se ajunge mai repede la o soluție "câștigătoare".

Pai da dar asta inseamna ca exista si o configuratie a inputului pe care sursa de 90 o rezolva si pe care ce de 100 nu:|.
 Nu am dreptate?

[•marcelcodrea]

Nu am citit problema dar din cum le descrie Cosmin Mihai Tutunaru comportamentul nu cred ca ai dreptate.

Doar daca exista mai multe posibilitati de a ajunge la o stare finala, s-ar putea ca doi algoritmi sa o ia pe doua carari corecte si sa ajunga unul mai repede decat altul la o "solutie castigatoare". Daca exista o singura carare corecta, atunci amandoi algoritmii o vor urma si vor ajunge in acelasi timp la "solutia castigatoare".

[•APOCALYPTO]

Am schimbat ordinea si am aplicat back pe ultimele 3 sferturi din input si apoi pe primul sfert.
Rezultat: tot 90 de puncte insa acum trece testul 2 si pica testul 10

[•mrares]

Are careva un test mai... ciudat?
Tot trimit surse si iau fisier corupt pe 9 teste, am facut 6 teste si imi da corect, nu stiu ce gresesc... iar testele de la oji nu le gasesc -_-;

[•S7012MY]

Din cate am vazut tu ai fisier de iesire corupt. Vezi sa ai numele corecte si inchide fisierele la sf. progamului

[•mrares]

La fel... altfel nu luam 10 pct