infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Stefan Istrate din Martie 07, 2010, 20:57:17



Titlul: 981 Immortal
Scris de: Stefan Istrate din Martie 07, 2010, 20:57:17
Aici puteti discuta despre problema Immortal (http://infoarena.ro/problema/immortal).


Titlul: Răspuns: 981 Immortal
Scris de: Ionescu Robert Marius din Martie 07, 2010, 21:48:53
Un pik ciudat sa se dea back la 11-12  :peacefingers:


Titlul: Răspuns: 981 Immortal
Scris de: Vlad Eugen Dornescu din Martie 07, 2010, 21:51:34
Un pik ciudat sa se dea back la 11-12  :peacefingers:

Cand se pun cele de la a 10-a ? :fighting:


Titlul: Răspuns: 981 Immortal
Scris de: Andrei Grigorean din Martie 08, 2010, 09:28:40
Astazi vor fi adaugate problemele de la clasele a IX-a si a X-a.


Titlul: Răspuns: 981 Immortal
Scris de: alexandru din Martie 08, 2010, 16:01:42
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


Titlul: Răspuns: 981 Immortal
Scris de: Andrei Popescu din Martie 08, 2010, 16:46:48
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.


Titlul: Răspuns: 981 Immortal
Scris de: alexandru din Martie 08, 2010, 17:08:45
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  :-s


Titlul: Răspuns: 981 Immortal
Scris de: Andrei Popescu din Martie 08, 2010, 17:28:35
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  :-s

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. :P


Titlul: Răspuns: 981 Immortal
Scris de: alexandru din Martie 08, 2010, 17:32:59
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  :-s


Titlul: Răspuns: 981 Immortal
Scris de: Andrei Popescu din Martie 08, 2010, 17:45:23
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  :-s

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.


Titlul: Răspuns: 981 Immortal
Scris de: alexandru din Martie 08, 2010, 18:23:50
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();
}
}
}


Titlul: Răspuns: 981 Immortal
Scris de: Dragos din Martie 10, 2010, 13:49:35
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!


Titlul: Răspuns: 981 Immortal
Scris de: Jurba Andrei din Martie 10, 2010, 15:14:51
Nu cred ca textul se refera la "The Immortal" :P 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.imdb.com/title/tt0091203/)
http://www.cinemagia.ro/filme/highlander-nemuritorul-2111/# (http://www.cinemagia.ro/filme/highlander-nemuritorul-2111/#)

Citat din mesajul lui: Connor MacLeod
There can be only one!





Titlul: Răspuns: 981 Immortal
Scris de: alexandru din Martie 10, 2010, 15:35:46
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 :)


Titlul: Răspuns: 981 Immortal
Scris de: Dragos din Martie 12, 2010, 14:03:05
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?


Titlul: Răspuns: 981 Immortal
Scris de: Adrian Budau din Martie 12, 2010, 21:11:00
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.


Titlul: Răspuns: 981 Immortal
Scris de: Dragos din Martie 13, 2010, 12:11:20
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. :sad:


Titlul: Răspuns: 981 Immortal
Scris de: Adrian Budau din Martie 13, 2010, 15:53:51
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".


Titlul: Răspuns: 981 Immortal
Scris de: Cosmin-Mihai Tutunaru din Martie 13, 2010, 19:40:35
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".


Titlul: Răspuns: 981 Immortal
Scris de: Dragos din Martie 13, 2010, 20:58:19
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?


Titlul: Răspuns: 981 Immortal
Scris de: Codrea Marcel din Martie 14, 2010, 00:29:19
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".


Titlul: Răspuns: 981 Immortal
Scris de: Dragos din Martie 14, 2010, 15:27:51
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


Titlul: Răspuns: 981 Immortal
Scris de: Mardare Rares din Noiembrie 23, 2010, 17:03:01
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 -_-;


Titlul: Răspuns: 981 Immortal
Scris de: Petru Trimbitas din Noiembrie 23, 2010, 17:04:33
Din cate am vazut tu ai fisier de iesire corupt. Vezi sa ai numele corecte si inchide fisierele la sf. progamului


Titlul: Răspuns: 981 Immortal
Scris de: Mardare Rares din Noiembrie 23, 2010, 17:20:52
La fel... altfel nu luam 10 pct


Titlul: Răspuns: 981 Immortal
Scris de: FMI-Balcau Ionut din Martie 15, 2011, 13:37:50
Stie cineva de unde pot lua testele de la oji? In arhiva la downloaduri, in evaluator sunt gresite testele (fisierele de iesire sunt aceleasi ca fisierele de intrare)

Imi da raspuns gresit pe primul test si fisier de iesire lipsa pe 3 altele :/ Nu pot sami dau seama de ce.


Titlul: Răspuns: 981 Immortal
Scris de: Parfene Narcis din Martie 15, 2011, 14:51:24
http://olimpiada.info/oji2010/index.php?cid=arhiva (http://olimpiada.info/oji2010/index.php?cid=arhiva)


Titlul: Răspuns: 981 Immortal
Scris de: Laurentiu Ion din Martie 17, 2011, 14:26:34
Tot ce pot sa spun e... CIUDAT  :-k :annoyed:

Am luat doar 90 de puncte cu TLE pe testul 2. Intr-adevar, pe testul 2 am 0.28 secunde deci depaseste 0.2. Daca schimb ordinea inputului, timpul de executie pe testul 2 devine 0.03 dar imi da "fisier de iesire corupt" pe 7 teste => 30 pct. De ce? tot ce fac e sa citesc jumate din nemuritori si sa ii pun in jumatatea a doua, iar cealalta jumate in prima jumatate a vectorului de nemuritori  :readthis:

Nu parcurg matricea, parcurg vectorul de nemuritori... metoda implementata e la fel cu cea care s-a discutat aici...

Am incercat sa afisez si cu streamuri si cu printf()...

Soo... de unde vine treaba cu "Fisier de iesire corupt"?


LE: pe .campion iau 100  :-'


Titlul: Răspuns: 981 Immortal
Scris de: Usurelu Catalin din Martie 17, 2011, 18:06:58
Pai insemna ca nu iti afiseaza nimic, sau nu afiseaza ceva.
Poata nu ai pus limita bine la un vector, si eu am patit la fel.


Titlul: Răspuns: 981 Immortal
Scris de: Chibici Tiberiu din Martie 17, 2011, 22:24:01
Eu am incercat sa rezolv cu un fel de back cu coada.

Pentru a obtine usor solutia la final, coada e structurata ca un arbore.

O mica problema ar fi ca un element din coada are 76 bytes (destul de mare), pentru ca in fiecare nod retin noua lista de nemuritori.
Cam asa arata structura:
Cod:
struct QueueItem
{
    Point From, To;
    int RemainingNoobs;
   
    int Parent;

    Point Noobs[15];
};

Iau doar 50 puncte din pacate.
Am facut rost de testul 2 de la OJI, care e unul care imi pica si cu 500MB de memorie alocati tot iese din coada.

Algoritmul meu este sa sortez vectorul Noobs la fiecare element din coada, in functie de distanta la fiecare din punctele pe care le contine.
Pentru elementele cu distanta 1 calculez directia, si vad daca pot sa sar peste. Daca e ocupata celula, inseamna ca exista un element cu distanta 4 pe directia respectiva.
Cand gasesc o pozitie unde pot sari, adaug in coada structura ce contine toate detaliile necesare.

Nu am avut nici un TLE, deci ma gandesc ca algoritmul e ok.

Aici (http://pastebin.com/PVGCAT7N) este toata sursa.


Titlul: Răspuns: 981 Immortal
Scris de: Laurentiu Ion din Martie 18, 2011, 09:38:38
Pai insemna ca nu iti afiseaza nimic, sau nu afiseaza ceva.
Poata nu ai pus limita bine la un vector, si eu am patit la fel.

Limita e buna ca am incercat testul respectiv si da corect, dar in 0.3 sec. Intrebarea e de ce daca schimb ordinea nemuritorilor imi da "Fisier corupt" pe 7 teste? ](*,)


Titlul: Răspuns: 981 Immortal
Scris de: Popescu Silviu din Iunie 26, 2011, 20:49:17
Testele sunt cam slabute :D, am luat suta parcurgand liniile invers :D


Titlul: Răspuns: 981 Immortal
Scris de: Sorin Rita din Decembrie 02, 2011, 14:03:20
Cred ca testul 3 nu respecta a doua restrictie :D


Titlul: Răspuns: 981 Immortal
Scris de: Junc Raul Cosmin din Februarie 17, 2012, 18:03:23
Salut!
Ma poate ajuta cineva? Am trimis sursa si primesc 40 de puncte pe ea, la 2 teste ii timp depasit, infine, dar ce ma dispera este ca la 4 teste primesc "Fisier de iesire corupt!" am citit despre eroarea asta si multi nu au scirs bine fisierul de iesire... Dar eu l-am scris bine si doar la 4 din ele primesc... Deci nu cred ca are legatura cu numele http://infoarena.ro/job_detail/681718

Multumesc pentru timpul acordat, succes in continuare.


Titlul: Răspuns: 981 Immortal
Scris de: Paul-Dan Baltescu din Februarie 17, 2012, 19:26:49
Am verificat pe calculatorul meu, chiar nu afisezi nimic pe testele respective.


Titlul: Răspuns: 981 Immortal
Scris de: Junc Raul Cosmin din Februarie 21, 2012, 00:30:44
Poti sa imi dai vre-un test care imi zice ca e gresit? Multumesc


Titlul: Răspuns: 981 Immortal
Scris de: FMIAnita Liviu din Martie 01, 2012, 18:03:19
Primesc la 9/10 teste "Fisier de iesire corupt!" .Am incercat sa fac cateva teste facute manual, si toate merg ok. Imi puteti da, va rog, un hint?   

Aici e codul : http://pastebin.com/UQ901B3W


Titlul: Răspuns: 981 Immortal
Scris de: Mihai Visuian din Octombrie 04, 2012, 19:44:24
Buna! Iau 30 de puncte, cu OK pe testele 4,5,8, iar pe restul am FISIER DE IESIRE CORUPT. M-am incadrat in limite si am inchis si fisierele. Imi puteti spune va rog unde gresesc sau ce pot corecta?


Titlul: Răspuns: 981 Immortal
Scris de: Adrian Budau din Octombrie 04, 2012, 20:31:01
Primesti acel mesaj("Fisier de iesire corupt") daca tu nu afisezi exact I - 1 linii cu 4 numere fiecare.
Aici s-ar afla problema la tine, vezi poate nu ramai cu un singur nemuritor la final.


Titlul: Răspuns: 981 Immortal
Scris de: Marian Iacob din Ianuarie 17, 2014, 15:44:22
pentru cei ce iau 90 puncte picand pe testul 2 parcurgeti nemuritorii in ordinea inversa ! (de la I la 1 nu de la 1 la I, I fiind numarul de nemuritori din enunt ) ! good luck!


Titlul: Răspuns: 981 Immortal
Scris de: Darius-Florentin Neatu din Februarie 08, 2014, 16:10:36
pentru cei ce iau 90 puncte picand pe testul 2 parcurgeti nemuritorii in ordinea inversa ! (de la I la 1 nu de la 1 la I, I fiind numarul de nemuritori din enunt ) ! good luck!
Si daca schimba un admin testul 2 si pune unul la care parcurgerea nu are importanta ?  :-'  S-a vorbit mai sus care e solutia optima.