•stef2n
|
|
« : Martie 07, 2010, 20:57:17 » |
|
Aici puteti discuta despre problema Immortal.
|
|
|
Memorat
|
Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
|
|
|
•Robytzza
|
|
« Răspunde #1 : Martie 07, 2010, 21:48:53 » |
|
Un pik ciudat sa se dea back la 11-12
|
|
|
Memorat
|
|
|
|
•dornescuvlad
|
|
« Răspunde #2 : Martie 07, 2010, 21:51:34 » |
|
Un pik ciudat sa se dea back la 11-12 Cand se pun cele de la a 10-a ?
|
|
|
Memorat
|
|
|
|
•wefgef
|
|
« Răspunde #3 : Martie 08, 2010, 09:28:40 » |
|
Astazi vor fi adaugate problemele de la clasele a IX-a si a X-a.
|
|
|
Memorat
|
omului i-au fost date instinctele pentru a supravietui, nu pentru a fi sclavul lor.
|
|
|
•alexandru92
|
|
« Răspunde #4 : 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
|
|
« Ultima modificare: Martie 08, 2010, 16:12:49 de către alexandru »
|
Memorat
|
|
|
|
•pandaemon
Strain
Karma: 4
Deconectat
Mesaje: 7
|
|
« Răspunde #5 : 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.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #6 : 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
|
|
|
Memorat
|
|
|
|
•pandaemon
Strain
Karma: 4
Deconectat
Mesaje: 7
|
|
« Răspunde #7 : 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 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.
|
|
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #8 : 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
|
|
|
Memorat
|
|
|
|
•pandaemon
Strain
Karma: 4
Deconectat
Mesaje: 7
|
|
« Răspunde #9 : 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 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.
|
|
« Ultima modificare: Martie 08, 2010, 17:55:31 de către Andrei Popescu »
|
Memorat
|
|
|
|
•alexandru92
|
|
« Răspunde #10 : Martie 08, 2010, 18:23:50 » |
|
Aceeasi chestie fac si eu.... LE: Asta e bucata de 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(); } } }
|
|
« Ultima modificare: Martie 08, 2010, 19:04:21 de către alexandru »
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #11 : 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!
|
|
|
Memorat
|
|
|
|
|
•alexandru92
|
|
« Răspunde #13 : 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
|
|
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #14 : 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?
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #15 : 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.
|
|
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #16 : 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.
|
|
|
Memorat
|
|
|
|
•freak93
|
|
« Răspunde #17 : 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".
|
|
|
Memorat
|
|
|
|
•stocarul
|
|
« Răspunde #18 : 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".
|
|
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #19 : 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?
|
|
|
Memorat
|
|
|
|
•marcelcodrea
|
|
« Răspunde #20 : 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".
|
|
|
Memorat
|
|
|
|
•APOCALYPTO
|
|
« Răspunde #21 : 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
|
|
|
Memorat
|
|
|
|
•mrares
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #22 : 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 -_-;
|
|
|
Memorat
|
|
|
|
•S7012MY
|
|
« Răspunde #23 : 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
|
|
|
Memorat
|
|
|
|
•mrares
Strain
Karma: -5
Deconectat
Mesaje: 21
|
|
« Răspunde #24 : Noiembrie 23, 2010, 17:20:52 » |
|
La fel... altfel nu luam 10 pct
|
|
|
Memorat
|
|
|
|
|